DOUG Lloyd: Hyvä, joten tässä kohdassa olet
luultavasti tuttuja jossa paneelit ja liittyvät luettelot
joka on kaksi pääasiallista tietorakenteita olemme
puhui pitää sarjaa tiedot samankaltaisten tietotyyppejä järjestetty.
>> Nyt aiomme puhua noin pari muunnelmia
koskevat taulukot ja linkitettyjen listojen.
Tässä videossa olemme menossa puhua pinot.
Erityisesti aiomme puhua noin datarakenne kutsutaan pino.
Recall aiempiin keskusteluihin noin viitteitä ja muisti,
että pino on myös nimenne segmentin muistia
jossa staattisesti ilmoitettu memory-- muisti, että olet
nimi, muuttujat annat nimeksi, et niin edelleen ja toiminta kehyksiä, jotka olemme myös
kutsupino kehyksiä olemassa.
Joten tämä on pino tietorakenne ei pino segmentti muistia.
OK.
>> Mutta mikä on pino?
Joten se on aika paljon vain erikoinen rakenne
joka ylläpitää tietoja järjestäytyneesti.
Ja siellä on kaksi hyvin yhteinen tapoja toteuttaa
pinot kahdella tietorakenteita että olemme jo tuttuja,
taulukot ja linkitettyjen listojen.
Mikä tekee pino erityinen on miten laitamme tiedot
pinoon, ja tapaamme poistaa tietoja pinosta.
Erityisesti pinot sääntö on vain kaikkein
viimeksi lisätyt elementti voidaan poistaa.
>> Joten ajattele sitä niin kuin se on pino.
Olemme paalutus tiedot itsensä päälle,
ja vain asia yläreunassa paalun voidaan poistaa.
Emme voi poistaa asia alla koska kaikki muu olisi
romahtaa ja kaatua.
Joten me todella olemme rakentamassa pinon Sitten täytyy poistaa pala palalta.
Tämän vuoksi me yleensä viitataan pinoon niin LIFO rakenne,
last in, first out.
LIFO, last in, first out.
>> Joten koska tämä rajoitus miten tieto voidaan lisätä
ja poistetaan pinosta, siellä oikeastaan vain kaksi asiaa voimme tehdä pino.
Voimme työntää, joka on termi käytämme lisäämiseen
uusi elementti alkuun pino, tai jos pino ei ole olemassa
ja Luomme sitä tyhjästä, luodaan pino ensinnäkin
olisi ajaa.
Ja sitten pop, että on sellainen CS termi käytämme poistaa viimeksi
lisätään elementti ylhäältä pinon.
>> Joten olemme menossa katsomaan molemmat toteutukset, molemmat array perustuu
ja linkitetty lista perustuu.
Ja aiomme aloittaa array perustuu.
Joten tässä on perusajatus, mitä array perustuu pino tietorakennetta
näyttäisi.
Meillä kirjoitetut määritelmä täällä.
Sisältä että meillä on kaksi jäsentä tai kenttiä rakenteen.
Meillä jono.
Ja taas olen käyttäen mielivaltaista tietotyyppi arvo.
>> Joten tämä voisi olla mikä tahansa tietotyyppi, int char tai eräitä muita tietoja
Kirjoita olet aiemmin luonut.
Joten meillä on taulukon koko kapasiteetin.
Kapasiteetti punta määritelty vakio, ehkä jossain muualla meidän tiedostoon.
Niin huomaa jo tämän tietyn täytäntöönpano olemme rajaava
itsemme oli tyypillisesti tapauksessa paneelit,
joita emme voi dynaamisesti muuttaa, missä on joitakin
elementtien maksimi että voimme laittaa meidän pinon.
Tässä tapauksessa se on kapasiteettia elementtejä.
>> Olemme myös seurata pinon.
Mikä elementti on kaikkein äskettäin lisätä pinoon?
Ja niin me seurata, että muuttujaan nimeltä alkuun.
Ja kaikki tämä saa käärittynä yhteen uuteen tietotyyppi nimeltään pino.
Ja kun me luoneet tämä uusi tietotyyppi
voimme käsitellä sitä kuin muita tietoja tyyppi.
Voimme julistaa pino s, kuten voisimme tehdä int x, tai char y.
Ja kun me sanomme pino s, hyvin, mitä tapahtuu
on saamme joukko muisti varattu meille.
>> Tässä tapauksessa kapasiteettia Olen ilmeisesti päättänyt
on 10 koska minulla yhden muuttujan tyypin pinon
joka sisältää kaksi kenttää muistaa.
Array, tässä tapauksessa on menossa olla joukko kokonaislukuja
kuten on laita suurimman osan esimerkeistä.
Ja toinen kokonaisluku muuttuja kykenee tallentamaan alkuun,
viimeksi lisätyt elementti pino.
Joten yksi pino mitä me aivan määritelty näyttää seuraavalta.
Se on laatikko sisältää joukko 10 mitä
on kokonaislukuja tässä tapauksessa ja toinen kokonaisluku muuttuja siellä vihreä
osoittamaan pinon päälle.
>> Asettaa alkuun pino me vain sanoa s.top.
Näin saimme pääsyn alan rakenne muistuttaa.
s.top ollessa 0 tehokkaasti ei tämä meidän pinoon.
Joten jälleen meillä on kaksi toimintaa että voimme tehdä nyt.
Emme voi työntää ja voimme pop.
Aloitetaan push.
Jälleen työntää lisää uuden elementti päällimmäinen.
>> Joten mitä me tarvitsemme tehdä tämän taulukon toteutuksesta?
Hyvin yleisesti push-toiminnon on menossa
tarvitse hyväksyä osoitin pino.
Nyt ottaa toisen ja miettiä sitä.
Miksi haluamme hyväksyä osoitin pino?
Recall edellinen videoita kiikaritähtäimellä ja osoittimia,
mitä tapahtuisi, jos me vain lähetetään pino, s pikemminkin kuin parametri?
Mitä todella välitetään siellä?
Muista Luomme kopio kun välitämme sen funktio
ellemme käytä osoittimia.
Ja niin tämä toiminto työntää tarpeisiin hyväksyä osoitin pinoon
niin että olemme todella muuttuu pino aiomme muuttaa.
>> Toinen asia push varmaan haluaa hyväksyä on tieto tyypin arvo.
Tässä tapauksessa, jälleen, kokonaisluku, joka aiomme lisätä huipulle pinon.
Joten meillä meidän kahden parametrit.
Mitä aiomme nyt tehdä sisällä push?
No, yksinkertaisesti, me vain aio lisätä että elementti huipulle pinon
ja sitten muuttaa, jos alkuun pino on, että s piste alkuun arvo.
Joten tämä on mitä funktio ilmoitus push
voisi näyttää vuonna array-pohjainen toteuttamista.
>> Tämäkään ei ole kova ja nopea sääntö että voisit muuttaa tätä ja on
se vaihtelee eri tavoin.
Ehkä s julistetaan maailmanlaajuisesti.
Ja niin sinun ei tarvitse edes siirtää se on parametrina.
Tämä on jälleen vain Yleinen tapaus push.
Ja on olemassa erilaisia tapoja toteuttaa se.
Mutta tässä tapauksessa meidän push vie
kaksi argumenttia, osoitin pino ja tieto tyypin arvo, kokonaisluku
tässä tapauksessa.
>> Joten me julisti s, me sanoi s.top ollessa 0.
Nyt työnnä numero 28 pinoon.
No mitä se tarkoittaa?
No tällä hetkellä pinon on 0.
Ja niin mitä pohjimmiltaan tulee tapahtumaan on
aiomme pysyä numero 28 osaksi array sijainti 0.
Melko yksinkertainen, oikea, että oli alkuun ja nyt olemme hyvä mennä.
Ja sitten meidän täytyy muuttaa mitä päällimmäinen on.
Niin että seuraavan kerran me push elementti,
aiomme tallentaa sen array sijainti, luultavasti ei 0.
Emme halua korvata mitä me vain laittaa sinne.
Ja niin me vain siirtyä ylhäältä 1.
Että luultavasti järkevää.
>> Nyt jos haluamme laittaa toinen elementti pinoon, että haluamme ajaa 33,
No nyt me vain vie 33 ja laita se array sijainti numero
1, ja sitten muuttaa kärkeen pino olla valikoimaan Sijainti numero kaksi.
Joten jos seuraavan kerran haluamme push elementti pinoon,
se tulee laittaa array sijainti 2.
Ja tehdään se vielä kerran.
Me ajaa 19 pois pinot.
Laitamme 19 array sijainti 2 ja muuttaa kärkeen pinon
olla array sijainti 3 joten jos seuraavan kerran
täytyy tehdä push olemme hyvä mennä.
>> OK, niin se työntää pähkinänkuoressa.
Entä popping?
Joten popping on eräänlainen vastine työntää.
Se miten me poistaa tietoja pino.
Ja yleensä pop tarpeisiin tehdä seuraavaa.
Se tarvitsee hyväksyä osoitin pino, jälleen yleisessä tapauksessa.
Joissakin muissa tapauksessa saatat ovat ilmoittaneet pino maailmanlaajuisesti,
jolloin sinun ei tarvitse siirtää sitä koska siihen on jo pääsy siihen
kuten globaali muuttuja.
Mutta sitten mitä muuta meidän täytyy tehdä?
No olimme monesko pinon push,
joten olemme luultavasti menossa haluavat dekrementoidaan pinon päälle
pop, eikö?
Ja sitten tietenkin olemme myös menossa haluavat
palauttaa arvon että poistamme.
Jos lisäämme elementtejä, haluamme päästä elementit ulos myöhemmin,
me luultavasti todella haluat tallentaa niitä niin me
älä vain poista ne pino ja sitten tehdä mitään heidän kanssaan.
Yleensä jos olemme työntämällä ja popping täällä
haluamme säilyttää tämän tiedot tarkoituksenmukaisella tavalla
ja niin se ei tee järkeä vain hävittää sen.
Joten tämä toiminto olisi luultavasti palata arvo meille.
>> Joten tämä on mitä ilmoitus pop voisi näyttää siellä ylhäällä vasemmalla.
Tämä toiminto palauttaa data tyypin arvo.
Jälleen olemme olleet käyttäen kokonaislukuja kaikkialla.
Ja se hyväksyy osoittimen pinon sen ainoa argumentti tai ainoa parametri.
Joten mitä on pop aikoo tehdä?
Sanotaan haluamme nyt pop elementti pois s.
Joten muistakaa Sanoin, että pinot ovat viime in, first out, LIFO tietorakenteita.
Joka elementti on menossa poistetaan pinosta?
Arvasit 19?
Koska olisit oikeassa.
19 oli viimeinen elementti lisäsimme pino kun olimme työntää elementtejä,
ja niin se tulee ensimmäinen elementti, joka saa poistaa.
Aivan kuin sanoimme 28, ja sitten laittaa 33 sen päälle,
ja laitamme 19 päälle, että.
Ainoa elementti voimme ottaa pois on 19.
>> Nyt kaavion täällä, mitä olen tehnyt on eräänlainen poistetaan 19 jono.
Se ei ole oikeastaan mitä aiomme tehdä.
Olemme juuri menossa eräänlainen ja teeskennellä se ei ole siellä.
Se on edelleen siellä että muistipaikka,
mutta me vain aio sivuuttaa sitä muuttamalla alkuun meidän pinon
olemasta 3-2.
Joten jos me nyt työntää toinen elementti pinoon,
se yli kirjoittaa 19.
>> Mutta älkäämme käydä läpi ongelmia poistamisen 19 pinosta.
Voimme vain teeskennellä se ei ole siellä.
Varten pinon se on mennyt, jos muutamme alkuun olevan 2 sijasta 3.
Selvä, joten se oli aika paljon se.
Siinä kaikki meidän täytyy tehdä pop elementti pois.
Tehdään se uudestaan.
Joten olen korostanut sen punaisella täällä osoittavat Teemme toisen puhelun.
Aiomme tehdä sama asia.
>> Joten mitä tulee tapahtumaan?
No, me aiomme säilyttää 33 x ja olemme menossa
muuttaa päällimmäinen 1.
Niin että jos me nyt työntää elementin pinon johon olemme
aikoo tehdä juuri nyt, mitä tulee tapahtumaan
on aiomme päälleäänittävän array Sijainti numero 1.
Jotta 33 joka oli tavallaan jäljellä takana me vain teeskenteli
jota ei enää ole, me vain menossa jotta hakata sitä ja laittaa 40 siellä sijaan.
Ja sitten tietenkin, koska teimme push,
aiomme kasvattaa pinon 1-2
niin että jos me nyt lisätä toinen elementti se tulee
mennä array Sijainti numero kaksi.
>> Nyt liittyvät luettelot ovat toinen tapa toteuttaa pinot.
Ja jos tämän määritelmän screen täällä näyttää tutulta,
se johtuu se näyttää melkein täsmälleen sama, itse asiassa,
se aika paljon on täsmälleen sama kuin yksinään linkitetty lista,
Jos muistatte meidän keskustelua yksittäin sidoksissa luetteloita toinen video.
Ainoa rajoitus tässä on meille ohjelmoijille,
emme saa lisätä tai poistaa satunnaisesti
alkaen yksittäin linkitetyn listan jota voisimme aiemmin tehdä.
Voimme vain nyt lisätä ja poistaa etu- tai yläosan linkitetyn
lista.
Se on todella ainoa ero kuitenkin.
Tämä on muuten yksittäin linkitetyn listan.
Se on vain rajoitus korvaa itsellemme
kuten ohjelmoijille, että muuttuu sen pinoon.
>> Sääntö täällä on aina säilyttää osoitin johtaja linkitetyn listan.
Tämä on tietysti yleisesti tärkeä sääntö ensin.
Saat yksittäin linkitetty lista muutenkin sinua tarvitsee vain osoitin päähän
jotta on, että ketju voitava siirtää
joka toinen elementti vuonna linkitetty lista.
Mutta se on erityisen tärkeää pino.
Ja niin yleensä olet menossa todella haluavat
tämä osoitin on globaali muuttuja.
Se luultavasti olla jopa helpompaa näin.
Mitkä ovat analogeja push ja pop?
Oikea.
Joten työntää taas on lisännyt uusi elementti pino.
Vuonna linkitetty lista, joka tarkoittaa, että menossa on
luoda uusi solmu, että olemme menossa lisätä osaksi linkitetty lista,
ja noudata varovaisia ​​askelia että olemme edellä on selostettu
vuonna yksittäin linkitettyjen listojen lisätä sen ketju rikkomatta ketjua
ja menettämättä tai orpoutumista tahansa elementtejä linkitetyn listan.
Ja se on periaatteessa mitä että pikku möykky tekstiä siellä tiivistää.
Ja lähdetään katsomaan sitä kuin kaavio.
>> Joten tässä on meidän linkitetty lista.
Se samanaikaisesti sisältää neljä osatekijää.
Ja täydellisemmin tässä meidän pino sisältää neljä elementtejä.
Ja sanotaanko haluamme nyt työntää uusi kohde päälle tämä pino.
Ja haluamme työntää uusi Tuote, jonka data-arvo on 12.
No mitä aiomme tehdä?
No ensimmäinen aiomme malloc tila, dynaamisesti
jakaa tilaa uusi solmu.
Ja tietenkin heti me soittaa malloc me aina
varmista tarkistaa null, koska jos meillä null takaisin
siellä oli jonkinlainen ongelma.
Emme halua dereference että null osoitin tai tulet kärsimään seg vika.
Tuo ei ole hyvä.
Joten olemme malloced solmun.
Oletamme meillä on ollut menestys täällä.
Aiomme laittaa 12 otetaan datakentässä, että solmun.
Nyt te muistatte joka meidän osoittimia siirtyy ensi joten emme katkaisemiseksi?
Meillä on pari vaihtoehtoa täällä, mutta ainoa, joka tulee olemaan turvallinen
on asettaa uutinen ensi osoitin kohta vanhaan johtaja luettelon
tai mitä pian vanha pää luettelon.
Ja nyt, että meidän kaikkien elementit ketjuttaa,
voimme vain siirtyä luettelon kohtaan samaan paikkaan, että uudet ei.
Ja olemme nyt käytännössä ajanut uusi elementti päälle edessä pinon.
>> Pop me vain haluamme poistaa että ensimmäinen elementti.
Ja niin periaatteessa mitä meidän on tehtävä täällä,
hyvin meidän täytyy löytää toinen elementti.
Lopulta että tulee uusi pää kun olemme poistaa ensimmäinen.
Joten meidän täytyy vain aloittaa alusta, siirtyä yksi eteenpäin.
Kun meillä otteen yksi eteenpäin siitä, missä olemme tällä hetkellä
ovat voimme poistaa ensimmäinen turvallisesti ja sitten voimme vain siirtää pään
osoittamaan, mikä oli Toinen termi ja sitten nyt
on ensimmäinen sen jälkeen solmu on poistettu.
>> Joten jälleen, kun tarkastellaan sitä kun kaavio me
haluavat nyt pop elementti pois tähän pinoon.
Joten mitä me teemme?
No me ensin luomassa uusi osoitin, joka menee
osoittamaan samaan paikkaan kuin pää.
Aiomme siirtää sen yhden paikan eteenpäin sanomalla Trav tasavertaisten
trav ensi esimerkiksi, joka edistäisi Trav osoitin yksi
asentoon eteenpäin.
Nyt kun meillä pitää ensimmäisen elementin
kautta osoitin kutsutaan luettelo, ja Toinen elementti läpi osoitin nimeltään
trav, voimme turvallisesti poistaa että ensimmäinen elementti pinosta
menettämättä loput Ketjun koska me
on tapa viitata toiseen osaan
välittämään tavalla osoitin kutsutaan trav.
>> Joten nyt voimme vapauttaa että solmu.
Voimme ilmainen luettelo.
Ja sitten kaikki meidän täytyy tehdä nyt on Siirrä lista viittaavat samaan paikkaan
että trav tekee, ja olemme tavallaan takaisin jossa aloitimme ennen kuin työnsi 12
on ensimmäinen paikka, oikea.
Juuri tässä me olimme.
Meillä oli tämän neljän elementin pino.
Lisäsimme viidesosa.
Työnsimme viidesosa elementin, ja sitten me
piipahti että viimeksi lisätty elementti perääntymään.
>> Se on oikeastaan ​​aika paljon kaikki on pinot.
Voit toteuttaa ne taulukot.
Voit toteuttaa ne liittyvät luettelot.
On, tietenkin, muiden tapoja toteuttaa niitä.
Periaatteessa syystä käyttäisi pinot on ylläpitää dataa siten,
että viimeksi lisätyt elementti on ensimmäinen asia olemme
menossa halua saada takaisin.
Olen Doug Lloyd, tämä on CS50.