Tietopino. Algoritmit ja tietorakenteet aloittelijoille: pinot ja jonot
– Igor (järjestelmänvalvoja)Tässä artikkelissa kerron sinulle mikä on pino, sekä miksi sitä tarvitaan ja missä sitä käytetään.
Suuri määrä tietoon liittyviä ongelmia soveltuu standardoituun ratkaisuun. Siksi ei ole yllättävää, että monille heistä on jo pitkään keksitty menetelmiä, termejä ja kuvauksia. Voit esimerkiksi kuulla usein sanoja, kuten pino. Se kuulostaa erittäin monimutkaiselta, mutta kaikki on paljon yksinkertaisempaa.
Pino- Tämä on tapa esittää samantyyppisiä tietoja (voit kutsua sitä yksinkertaisesti tyypiksi) LIFO-järjestyksessä (Last In - First Out, mikä tarkoittaa "ensimmäinen sisään - viimeinen ulos"). On syytä mainita, että venäläisessä tekniikassa sitä kutsutaan myös "lehdeksi". Ja emme puhu siitä ruokakauppa, mutta torvista, jossa on patruunat aseita varten, koska periaate on hyvin samanlainen - ensimmäistä asetettua patruunaa käytetään viimeisenä.
Huomautus: On syytä tietää, että tällä sanalla voi olla muita merkityksiä. Siksi, jos puhe ei koske tietokoneita, on järkevää selventää.
Ymmärtääkseni paremmin, annan esimerkki elämästä. Oletetaan, että sinulla on pino lakanoita. Asetat jokaisen kirjoitetun paperiarkin sen viereen ja jokaisen seuraavan muiden päälle. Jos haluat saada esimerkiksi aivan ensimmäisen arkin tuloksena olevasta pinosta, sinun on vedettävä kaikki muut arkit ulos. Tämä on sama periaate, jolla pino on suunniteltu. Toisin sanoen jokaisesta viimeisestä lisätystä elementistä tulee ylin ja saadaksesi esimerkiksi aivan ensimmäisen elementin, sinun on vedettävä kaikki muut pois.
Mitä varten pino on? Päätarkoituksena on ratkaista tyypillisiä ongelmia, joissa on tarpeen ylläpitää jonkin tilasarjaa tai missä tarvitaan tietojen käänteistä esitystä (eli päinvastaiseen suuntaan).
Tietojenkäsittelyssä pinoa käytetään laitteistoissa (kuten prosessorissa), käyttöjärjestelmässä ja monissa ohjelmissa. Jos tarkastellaan esimerkkiä, jonka lähes kaikki ohjelmoineet ovat tuttuja, niin ilman pinorekursiota ei olisi mahdollista, koska jokaiselle paluu sinun on tallennettava se toimintoon Nykyinen tila Palauta tämä tila (eli vain LIFO-sekvenssi) nopeasti yläreunassa ja jokaisen funktiosta poistumisen yhteydessä. Ja jos kaivetaan vielä syvemmälle, niin periaatteessa koko lähestymistapa ohjelmien käynnistämiseen ja suorittamiseen perustuu pinon periaatteeseen, jossa ennen seuraava ohjelma, käynnistetään päätilasta, suoritetaan, edellisen tila työnnetään pinoon niin, että kun käynnissä oleva sovellus tai aliohjelma on suorittanut loppuun, edellinen ohjelma jatkoi suoritustaan normaalisti siitä, mihin se pysähtyi.
Mitkä ovat pinon toiminnot? Päätoimintoja on vain kaksi:
1. Elementin lisääminen pinon yläosaan kutsutaan työntää
2. Uutteet yläelementti nimeltään pop
Mutta voit myös ajoittain törmätä toteutukseen, jossa yläelementti luetaan purkamatta sitä - ns kurkistaa.
Miten pino on järjestetty? Tyypillisesti pino toteutetaan kahdella tavalla:
1. Käyttämällä taulukkoa ja muuttujaa, joka osoittaa pinon yläosassa olevaan soluun
2. Linkitettyjen luetteloiden käyttäminen
Jokaisella näistä kahdesta vaihtoehdosta on hyvät ja huonot puolensa. Esimerkiksi, aiheeseen liittyvät luettelot käytön kannalta turvallisempi, koska jokainen lisätty elementti on sijoitettu dynaamisesti luotuun rakenteeseen (elementtien lukumäärässä ei ole ongelmia - ei ole turva-aukkoja, jotka sallivat vapaan liikkumisen ohjelmamuistissa). Säilytyksen ja käyttönopeuden kannalta ne ovat kuitenkin vähemmän tehokkaita (vaatii ylimääräinen sänky osoittimien tallentamiseen; hajallaan muistissa sen sijaan, että ne sijaitsevat peräkkäin, kuten taulukoissa).
Nyt tiedät, mikä pino on, sekä miksi sitä tarvitaan ja mihin sitä käytetään.
Stack on ohjelmointiilmiö ja luonnollinen ratkaisu. Pino tuli välittömästi tietokonealalle ja siitä tuli niin "natiivi", ikään kuin siitä kaikki alkoi.
Ilman pinoa prosessori ei toimi, ei ole rekursiota, ja tehokkaiden toimintokutsujen järjestäminen on mahdotonta. Mikä tahansa algoritmi pärjää ilman jonoa, luetteloa, kokoelmaa, taulukkoa tai järjestettyjen objektien järjestelmää, mutta mikään ei toimi ilman muistia ja pinoa, mukaan lukien kaikki edellä mainitut.
Alun kynnyksellä: prosessori, muisti ja pino
Ihanteellinen muisti tarjoaa osoitteen suoraan arvoon - nämä ovat korkean tason kone- ja kielitasoja. Ensimmäisessä tapauksessa prosessori iteroi peräkkäin muistiosoitteiden läpi ja suorittaa käskyjä. Toisessa tapauksessa ohjelmoija käsittelee taulukoita. Molemmat jaksot sisältävät:
- osoite = arvo;
- indeksi = arvo.
Osoite voi olla absoluuttinen ja suhteellinen, indeksi voi olla digitaalinen ja assosiatiivinen. Osoite ja indeksi voivat sisältää muun osoitteen kuin arvon, mutta nämä ovat epäsuoran osoittamisen yksityiskohtia. Ilman muistia prosessori ei voi toimia, ja ilman komentojen ja tietojen pinoa se on kuin vene ilman airoja.
Lautaspino on perinteinen tarina pinon olemuksesta: pinon käsitteestä ja käännöksestä yhteisessä tietoisuudessa. Et voi ottaa lautasta alhaalta, voit ottaa sen vain ylhäältä, ja sitten kaikki lautaset ovat ehjiä.
Se mikä tulee pinossa viimeisenä, menee ensin. Täydellinen ratkaisu. Pohjimmiltaan pino, toimintojen käännöksenä toiseksi, muuttaa idean algoritmista toimintosarjaksi.
Pinon olemus ja käsite
Prosessori ja muisti - pää rakenneosat tietokone. Prosessori suorittaa käskyjä, käsittelee muistiosoitteita ja hakee ja muuttaa arvoja näissä osoitteissa. Ohjelmointikielessä tämä kaikki muunnetaan muuttujiksi ja niiden arvoiksi. Pinon olemus ja viimeinen ensin ulos (LIFO) -konsepti pysyvät ennallaan.
Lyhennettä LIFO ei enää käytetä niin usein kuin ennen. Luultavasti siksi, että listat on muunnettu objekteiksi ja FIFO-jonoja käytetään tarpeen mukaan. Tietotyyppien dynamiikka on menettänyt merkityksensä muuttujien kuvauksen yhteydessä, mutta on saanut merkityksensä lausekkeiden suoritushetkellä: tiedon tyyppi määräytyy sen käyttöhetkellä, ja siihen asti voidaan kuvata. mitä tahansa ja miten haluat.
Joten pino - mikä se on? Nyt tiedät, että tämä on sopimaton kysymys. Loppujen lopuksi ilman pinoa ei ole moderni ohjelmointi. Mikä tahansa funktiokutsu tarkoittaa parametrien ja paluuosoitteen välittämistä. Funktio voi kutsua toista funktiota - tämä taas välittää parametreja ja paluuosoitetta. Arvojen kutsumismekanismin luominen ilman pinoa on ylimääräistä työtä, vaikka saavutettavissa oleva ratkaisu on varmasti mahdollinen.
Monet ihmiset kysyvät: "Pino - mikä se on?" Funktiokutsun yhteydessä se koostuu kolmesta toiminnosta:
- palautusosoitteen tallentaminen;
- tallentaa kaikki siirretyt muuttujat tai osoitteet niihin;
- toimintokutsu.
Kun kutsuttu toiminto on suorittanut tehtävänsä, se yksinkertaisesti palauttaa ohjauksen palautusosoitteeseen. Funktio voi kutsua mitä tahansa muita toimintoja, koska raja on vain pinon koko.
Pinon ominaisuudet
Pino ei ole abstrakti tietotyyppi, vaan todellinen mekanismi. Prosessoritasolla se on "moottori", joka jalostaa ja täydentää pääprosessorisyklin työtä. Kuten bittiaritmetiikka, pino tallentaa yksinkertaiset ja ilmeiset toimintasäännöt. Se on luotettava ja turvallinen.
Pinon tunnusomaisia ominaisuuksia ovat sen koko ja elementtien pituus. Prosessoritasolla kaiken määrää bittikapasiteetti, muistin osoitus ja siihen pääsyn fysiikka. Mielenkiintoinen ominaisuus ja perinne: pino kasvaa alaspäin, eli kohti väheneviä muistiosoitteita ja ohjelma- ja datamuisti - ylöspäin. Tämä on yleistä, mutta ei pakollista. Merkitys tässä on tärkeä - hän tuli viimeisenä ja lähti ensimmäisenä. Tämän yllättävän yksinkertaisen säännön avulla voit rakentaa mielenkiintoisia algoritmeja, jotka toimivat ensisijaisesti kielillä korkeatasoinen. Nyt et kysy, mikä on pino?
Moitteeton työ laitteisto on ollut normi jo pitkään, mutta eturintamassa tietotekniikat Ajatus pinosta on saamassa uusia ja lupaavia sovelluksia.
Pohjimmiltaan sillä ei ole väliä, mikä pino on prosessoritasolla. Se on luonnollinen osa tietokonearkkitehtuuria. Mutta ohjelmoinnissa pino riippuu tietystä sovelluksesta ja ohjelmoijan kyvystä.
Taulukot, kokoelmat, luettelot, jonot... Pino!
Ihmiset kysyvät usein kysymyksen: "Pino - mikä se on?" "Ohjelmointi" ja "järjestelmästäminen" ovat mielenkiintoisia käsitteitä: ne eivät ole synonyymejä, mutta ne liittyvät läheisesti toisiinsa. Ohjelmointi on mennyt niin pitkälle hyvin nopeasti, että saavutetut huiput näyttävät ihanteellisilta. Näin ei todennäköisesti ole. Mutta ilmeisesti jotain muuta.
Ajatus pinosta on tullut tutuksi paitsi tasolla eri kieliä ohjelmointia, mutta myös niiden suunnittelun ja tietotyyppien luontikyvyn tasolla. Kaikissa taulukoissa on push ja pop sekä käsitteet "first and viimeinen elementti"Matriisielementeistä" on tullut perinteisiä. Aikaisemmin oli vain taulukkoelementtejä, mutta nykyään niitä on:
- matriisin elementit;
- taulukon ensimmäinen elementti;
- taulukon viimeinen elementti.
Elementin sijoittaminen taulukkoon siirtää osoitinta, ja elementin hakeminen taulukon alusta tai sen lopusta vaikuttaa asiaan. Pohjimmiltaan tämä on sama pino, mutta sitä sovelletaan muihin tietotyyppeihin.
On erityisen huomionarvoista, että suosituilla ohjelmointikielillä ei ole pinorakennetta. Mutta he tarjoavat hänen ideansa kehittäjälle kokonaisuudessaan.
IBM teki dramaattisen virheen, kun se ei toimittanut pinon laitteistototeutusta. Tämä sarja sisälsi monia muita huonoja päätöksiä, mutta valitettavasti se kopioitiin Neuvostoliitossa nimellä ES EVM (Unified Series), ja kaikki sen omat kehitystyöt keskeytettiin. Tämä siirsi Neuvostoliiton teollisuuden tietokonekehityksessä monta vuotta taaksepäin.Jonottaa
Jono tietorakenteena on ymmärrettävä myös ohjelmointiin tuntemattomille. Jono sisältää elementtejä ikään kuin rivissä peräkkäin ketjussa. Jonolla on alku ja loppu. Voit lisätä uusia elementtejä vain jonon loppuun, voit ottaa elementtejä vain alusta. Toisin kuin tavallisessa jonossa, joka voidaan aina haluttaessa jättää pois, elementtejä ei voi poistaa ohjelmoijan jonon keskeltä.
Jonoa voidaan pitää putkena. Voit lisätä palloja - jonon osia - putken toiseen päähän, ja ne poistetaan toisesta päästä. Jonon keskellä olevat elementit, ts. putken sisällä oleviin palloihin ei pääse käsiksi. Putken pää, johon pallot lisätään, vastaa jonon loppua, pää, josta ne poistetaan, vastaa jonon alkua. Siten putken päät eivät ole symmetrisiä, putken sisällä olevat pallot liikkuvat vain yhteen suuntaan.
Periaatteessa voisimme sallia elementtien lisäämisen jonon molempiin päihin ja ottamista myös molemmista päistä. Tällainen tietorakenne on olemassa myös ohjelmoinnissa, sen nimi on "dec", englannista. Double Ended Queue, ts. jono, jossa on kaksi päätä. Joulukuuta käytetään paljon harvemmin kuin jonoa.
Jonon käyttö ohjelmoinnissa on lähes identtinen sen roolin kanssa jokapäiväisessä elämässä. Jono liittyy lähes aina huoltopyyntöihin, jos niitä ei voida suorittaa välittömästi. Jono ylläpitää myös pyyntöjen toimitusjärjestystä. Mieti esimerkiksi, mitä tapahtuu, kun henkilö painaa tietokoneen näppäimistön näppäintä. Näin ollen henkilö pyytää tietokonetta suorittamaan jonkin toiminnon. Jos hän esimerkiksi yksinkertaisesti kirjoittaa tekstiä, toiminnon tulisi sisältää yhden merkin lisääminen tekstiin, ja siihen voidaan liittää näytön alueen uudelleenpiirtäminen, ikkunan vierittäminen, kappaleen uudelleenmuotoilu jne.
Mikä tahansa, jopa yksinkertaisin, käyttöjärjestelmä aina moniajo jossain määrin. Tämä tarkoittaa, että näppäintä painettaessa käyttöjärjestelmä voi olla varattu johonkin muuhun työhön. Käyttöjärjestelmällä ei kuitenkaan ole oikeutta sivuuttaa näppäinpainallusta missään tilanteessa. Siksi tietokoneen toiminta keskeytyy, se muistaa tilansa ja siirtyy käsittelemään näppäinpainalluksia. Tämän käsittelyn tulee olla hyvin lyhyt, jotta se ei häiritse muita tehtäviä. Näppäimen painalluksella annettu komento lisätään yksinkertaisesti suoritusta odottavien pyyntöjen jonon loppuun. Tämän jälkeen keskeytys päättyy, tietokone palaa tilaan ja jatkaa näppäintä painamalla keskeytettyä työtä. Jonossa olevaa pyyntöä ei suoriteta heti, vaan vasta kun on sen vuoro.
Järjestelmässä Windows toimii ikkunalliset sovellukset perustuvat viesteihin, jotka lähetetään näille sovelluksille. Siellä on esimerkiksi viestejä hiiren painikkeen painamisesta, ikkunan sulkemisesta, tarpeesta piirtää ikkuna-alue uudelleen, valikkokohdan valinnasta jne. Jokaisella ohjelmalla on pyyntöjono. Kun ohjelma vastaanottaa suoritusaikaosan, se valitsee seuraavan pyynnön jonon edestä ja suorittaa sen. Siten ikkunoidun sovelluksen työ koostuu yksinkertaisesti sanottuna pyyntöjen suorittamisesta peräkkäin sen jonosta. Jonoa ylläpitää käyttöjärjestelmä.
Lähestymistapa ohjelmointiin, joka ei koostu suorista kutsuista proseduuriin, vaan lähetettyjen viestien lähettämisestä pyyntöjono, on monia etuja ja on yksi olio-ohjelmoinnin ominaisuuksista. Joten esimerkiksi jos ikkunaohjelma joutuu jostain syystä sammumaan, on parempi olla kutsumatta shutdown-komentoa välittömästi, mikä on vaarallista, koska se rikkoo työn logiikan ja voi johtaa tietojen katoamiseen. Sen sijaan ohjelma lähettää itselleen viestin suljettavaksi, joka lähetetään pyyntöjono ja toteutetaan aiemmin saatujen pyyntöjen jälkeen.
Taulukkopohjainen jonototeutus
Kuten jo sanottiin, ohjelmoijalle annetaan ylhäältä taulukko, jonka perusteella on toteutettava kaikki muut tietorakenteet. Tietenkin tällainen toteutus voi olla monivaiheinen, eikä matriisi aina toimi välittömänä toteutuspohjana. Jonon tapauksessa kaksi suosituinta toteutusta ovat jatkuva array-pohjainen toteutus, jota kutsutaan myös rengaspuskuripohjaiseksi toteutukseksi, ja referenssitoteutus tai luettelopohjainen toteutus. Viitetoteutukset käsitellään alla.
Jatkuvaa jonoa toteutettaessa kanta on kiinteäpituinen N joukko, joten jono on rajoitettu eikä se voi sisältää enempää kuin N elementtiä. Matriisielementtien indeksit vaihtelevat välillä 0 - N-1. Jonototeutus tallentaa taulukon lisäksi kolme yksinkertaista muuttujaa: jonon alun indeksin, jonon lopun indeksin ja jonoelementtien lukumäärän. Jonon elementit sisältyvät matriisin segmenttiin aloitusindeksistä loppuindeksiin.
Kun jonon loppuun lisätään uusi elementti, loppuindeksiä kasvatetaan ensin yhdellä ja sitten uusi elementti kirjoitetaan taulukkosoluun tällä indeksillä. Vastaavasti haettaessa elementtiä jonon päähakemistosta tallennetaan toiminnon tuloksena jonon pääindeksin sisältävän taulukkosolun sisältö, jonka jälkeen jonon pääindeksiä kasvatetaan yhdellä. Sekä jonon aloitus- että loppuindeksi liikkuvat toiminnan aikana vasemmalta oikealle. Mitä tapahtuu, kun jonon loppuindeksi saavuttaa taulukon lopun, ts. N-1?
Jonon toteutuksen avainideana on, että matriisi on henkisesti silmoitettu renkaaseen. Taulukon viimeistä elementtiä seuraa sen ensimmäinen elementti (muista, että viimeisen elementin indeksi on N - 1 ja ensimmäisen indeksi 0). Siirrettäessä jonon lopun indeksiä oikealle, siinä tapauksessa, että se osoittaa taulukon viimeiseen elementtiin, se siirtyy ensimmäiseen elementtiin. Siten jonon elementtien miehittämä taulukon jatkuva segmentti voi kulkea taulukon lopusta sen alkuun.
Pino
Pino on ohjelmoinnin suosituin ja ehkä tärkein tietorakenne. Pino on tallennuslaite, josta elementit poistetaan niiden lisäämisen käänteisessä järjestyksessä. Se on kuin epäsäännöllinen jono, jossa ensimmäisenä palvellaan se, joka pääsi viimeisenä. Ohjelmointikirjallisuudessa lyhenteet hyväksytään yleisesti kuvaamaan jonon ja pinon kurinalaisuutta. Jonokuri on nimetty FIFO, mikä tarkoittaa First In First Out. Pinon laji on nimetty LIFO, last in first out (Last In First Out).
Pino voidaan ajatella putkena, jossa on jousikuormitettu pohja ja joka sijaitsee pystysuorassa. Putken yläpää on avoin, elementtejä voidaan lisätä tai, kuten sanotaan, työntää siihen. Yleisesti hyväksytty Englanninkieliset termit tässä suhteessa ne ovat erittäin värikkäitä, kun elementin lisääminen pinoon on nimeltään push, käännettynä "työnnä, työnnä". Uusi lisättävä elementti työntää pinoon aiemmin asetetut elementit yhden aseman alaspäin. Kun elementit pompataan pinosta, ne työnnetään ylöspäin, englanniksi pop ("ampua").
Esimerkki pinosta olisi heinäsuovasta, pino papereita pöydällä, pino lautasia jne. Tästä tulee nimi pino, joka tarkoittaa pinoa englanniksi. Levyt poistetaan pinosta päinvastaisessa järjestyksessä niiden lisäämisessä. Vain ylälevyyn pääsee käsiksi, ts. lautanen pinon päällä. Hyvä esimerkki toimii myös rautatien umpikujana, johon voidaan pinota vaunuja.
Pinon käyttö ohjelmoinnissa
Pinoa käytetään melko usein ja useimmissa erilaisia tilanteita. Niitä yhdistää seuraava tavoite: sinun on tallennettava työ, jota ei ole vielä suoritettu, jos sinun on vaihdettava toiseen tehtävään. Pinoa käytetään väliaikaisesti sellaisen tehtävän tilan tallentamiseen, jota ei ole vielä suoritettu. Tilan tallennuksen jälkeen tietokone vaihtaa toiseen tehtävään. Kun se on suoritettu, siirretyn tehtävän tila palautetaan pinosta ja tietokone jatkaa keskeytettyä toimintaa.
Miksi pinoa käytetään keskeytetyn työn tilan tallentamiseen? Oletetaan, että tietokone suorittaa tehtävää A. Sen toteuttamisprosessissa herää tarve suorittaa tehtävä B. Tehtävän A tila muistetaan ja tietokone siirtyy suorittamaan tehtävää B. Mutta vaikka suoritettaisiin tehtävää B, tietokone voi vaihtaa toiseen tehtävään C, ja sen on tallennettava tehtävän B tila ennen siirtymistä tehtävään C. Myöhemmin, kun tehtävä C on suoritettu, palautetaan ensin tehtävän B tila, sitten tehtävän B suorittamisen jälkeen tehtävän A tila palautetaan. Siten palautus tapahtuu tallennuksen käänteisessä järjestyksessä, mikä vastaa pinon kurinalaisuutta.
Pinon avulla voit järjestää rekursion, ts. aliohjelma kutsuu itseään joko suoraan tai muiden kutsujen ketjun kautta. Suorittakoon esimerkiksi alirutiini A algoritmi riippuen syöttöparametri X ja mahdollisesti globaalien tietojen tila. Useimmille yksinkertaiset arvot X-algoritmi toteutetaan suoraan. Enemmän tapauksessa monimutkaisia merkityksiä X-algoritmi toteutetaan vähennyksenä saman algoritmin soveltamiseen X:n yksinkertaisemmille arvoille. Tässä tapauksessa alirutiini A viittaa itseensä ja välittää parametrina yksinkertaisemman arvon X. Tällä pääsyllä parametrin X edellinen arvo sekä kaikki alirutiinin A paikalliset muuttujat tallennetaan pinoon. Seuraava luodaan uusi setti paikalliset muuttujat ja muuttuja, joka sisältää parametrin X uuden (yksinkertaisemman) arvon. Kutsuttu alirutiini A toimii uudella muuttujajoukolla tuhoamatta edellistä joukkoa. Puhelun lopussa vanha paikallismuuttujajoukko ja syöteparametrin X vanha tila palautetaan pinosta ja rutiini jatkuu siitä mihin se jäi.
Itse asiassa sinun ei tarvitse edes tallentaa aliohjelman paikallisten muuttujien arvoja pinoon erityisellä tavalla. Tosiasia on, että aliohjelman paikalliset muuttujat (eli sen sisäiset, toimintamuuttujat, jotka luodaan sen suorittamisen alussa ja tuhotaan lopussa) sijoitetaan pinoon, joka on toteutettu laitteistolla tavanomaisten RAM-muisti. Työnsä alussa aliohjelma nappaa pinosta tilaa paikallisille muuttujilleen, tätä laitteistopinon muistialuetta kutsutaan yleensä paikallinen muuttujalohko tai englanniksi kehys("kehys"). Työnsä päätyttyä aliohjelma vapauttaa muistia poistamalla pinosta lohkon paikallisista muuttujistaan.
Paikallisten muuttujien lisäksi laitteistopinoon on tallennettu aliohjelman kutsujen paluuosoitteet. Kutsutaan aliohjelma jossain vaiheessa ohjelmaa A B. Ennen kuin alirutiini B kutsutaan, B:tä kutsuvaa käskyä seuraavan käskyn osoite tallennetaan pinoon. Tämä on ns palautusosoite ohjelmoida A. Kun se on suoritettu, alirutiini B ponnahtaa ohjelman A paluuosoitteen pinosta ja palauttaa ohjauksen tähän osoitteeseen. Tällöin tietokone jatkaa ohjelman A suorittamista aloittaen kutsukäskyä seuraavasta käskystä. Useimmissa prosessoreissa on erikoisjoukkueet, jotka tukevat aliohjelman kutsumista työntämällä ensin paluuosoite pinoon ja palaamalla aliohjelmasta pinosta ponnahtamaan osoitteeseen. Yleensä kutsukomentoa kutsutaan nimellä call, paluukomentoa kutsutaan paluuksi.
Myös aliohjelman tai funktion parametrit työnnetään pinoon ennen kuin sitä kutsutaan. Järjestys, jossa ne sijoitetaan pinoon, riippuu korkean tason kielten käytännöistä. Joten C- tai C++-kielessä ensimmäinen funktion argumentti on pinon yläosassa, toinen sen alapuolella ja niin edelleen. Pascalissa se on päinvastoin: funktion viimeinen argumentti on pinon yläosassa. (Siksi muuten, toimii kanssa muuttuva numero argumentit, kuten printf, joita Pascalilla ei ole.)
Fortran-4:ssä, yhdessä vanhimmista ja menestyneimmistä ohjelmointikielistä, argumentit välitetään erityisen muistialueen läpi, joka ei välttämättä sijaitse pinossa, koska 1900-luvun 70-luvun loppuun asti siellä oli vielä tietokoneita, kuten IBM 360- tai ES-tietokoneet ilman laitteistototeutuspinoa. Paluuosoitteita ei myöskään tallennettu pinoon, vaan kullekin aliohjelmalle vahvistettuihin muistisoluihin. Ohjelmoijat kutsuvat tällaista muistia staattiseksi siinä mielessä, että staattiset muuttujat ovat aina saman paikan muistissa aina kun ohjelma on käynnissä. Vain käytettynä staattinen muisti rekursio ei ole mahdollista, koska uusi kutsu tuhoaa paikallisten muuttujien aikaisemmat arvot. Viite Fortran 4 käytti vain staattisia muuttujia, ja rekursio oli kielletty. Tähän asti Fortran-kieltä on käytetty laajalti tieteellisissä ja teknisissä laskelmissa, mutta moderni standardi Fortran 90 on jo esitelty pino muisti, poistaa puutteet aikaisemmat versiot Kieli.
Array-pohjainen pinon toteutus
Taulukkopohjainen pinototeutus on ohjelmoinnin klassikko. Joskus edes pinon käsitettä ei tunnisteta täysin oikein tämän toteutuksen kanssa.
Toteutuksen pohjana on N-kokoinen matriisi, mikä toteuttaa rajoitetun kokoisen pinon, jonka suurin syvyys ei saa ylittää N. Matriisisoluindeksit vaihtelevat välillä 0 - N-1. Pinoelementit tallennetaan taulukkoon seuraavasti: pinon alaosassa oleva elementti sijaitsee taulukon alussa, ts. solussa, jonka indeksi on 0. Ylimpänä oleva elementti pohjaelementti pino, tallennettu indeksiin 1 ja niin edelleen. Pinon yläosa on tallennettu jonnekin taulukon keskelle. Pinon yläosassa olevan elementin indeksi on tallennettu erityiseen muuttujaan, jota kutsutaan yleisesti osoitin N - 1 . Pinoelementit vievät vierekkäisen osan taulukosta alkaen solusta, jonka indeksi on tallennettu pinoosoittimeen, ja päättyen taulukon viimeiseen soluun. Tässä vaihtoehdossa pino kasvaa indeksien laskun suuntaan. Jos pino on tyhjä, pinoosoitin sisältää arvon N (joka on yksi suurempi kuin taulukon viimeisen solun indeksi).
Ohjelmoinnin hallinnassa herää ennemmin tai myöhemmin kysymys: " Mikä on pino?".
Mielestäni ilmeisin tapa selittää tämä on kokoonpanokieliohjelma (älä huolestu), joka yksinkertaisesti lisää dataa pinoon.
Pino on kaikkeen ohjelmoitavaan tekniikkaan kuuluva tietorakenne. Useimmiten pinon toimintaperiaatetta verrataan lautaspinoon: ottaaksesi toisen ylhäältä, sinun on poistettava ylin. Pinoa kutsutaan usein lippaaksi - analogisesti ampuma-aseessa olevan lippaan kanssa (ammunta alkaa viimeksi ladatusta patruunasta).
Miksi kaikkea tätä tarvitaan?
Voit tuskin kirjoittaa ohjelmaa, joka ei käytä funktioita (alirutiineja). Kun funktiota kutsutaan, osoite kopioidaan pinoon palatakseen annetun aliohjelman suorituksen päätyttyä. Suorituksensa lopussa osoite palautetaan pinosta ohjelmalaskuriin ja ohjelman suorittamista jatketaan funktion jälkeisestä pisteestä.
Myös tässä aliohjelmassa käytetyt rekisterit on asetettava pinoon (korkeammilla kielillä kääntäjä tekee tämän).
Kaikki yllä oleva on tyypillistä niin sanotulle laitteistopinolle. Toivon, että ymmärrät, että tämä tietorakenne (LIFO - last in, first out) on hyödyllinen paitsi matalalla tasolla työskenneltäessä. Usein on tarve tallentaa tiedot tässä järjestyksessä (esimerkiksi tunnettu aritmeettisten lausekkeiden jäsentämisalgoritmi perustuu pinon kanssa työskentelemiseen), sitten ohjelmoijat toteuttavat ohjelmistopinon.
Kuinka se toimii?
Katsotaanpa tarkastellaan pinon kanssa työskentelemistä käyttämällä esimerkkiä MSP430-perheohjaimista. Valitsin ne vain siksi, että minulla oli ympäristö asennettuna työskentelemään niiden kanssa.
MSP430:ssa pino perustuu esi-dekrementaaliseen suunnitteluun. Nuo. Ennen kuin kirjoitat tietoja pinoon, se vähentää pinon yläosan osoitetta (ylälevy). On myös post-decremental/post-inkremental (pinon yläosan vähennys/lisäys tapahtuu datan kirjoittamisen jälkeen) ja preinkrementaalinen (ennen kirjoittamista yläosan osoitetta kasvatetaan).
Jos pino kasvattaa osoitettaan dataa kirjoitettaessa, sen sanotaan kasvavan ylöspäin, jos se pienenee, sen sanotaan kasvavan alaspäin.
SP-rekisteri vastaa pinon yläosan osoitteen tallentamisesta.
Kuten näet, oletusvertex-osoite on 0x0A00.
Harkitse tätä ohjelmaa:
PUSH #0123h ; 0123h:n asettaminen pinon päälle (TOS); kopioi tiedot muistista MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; kirjoita vielä kaksi numeroa PUSH #9250h PUSH #0000h ; pop-data pinosta POP R8 POP R9 POP R10
Mitä tämä ohjelma tekee?
PUSH-komennolla työnnetään tiedot 0123h pinoon. Näyttäisi siltä, että tällä komennolla kirjoitamme 0123h muistiin osoitteeseen 0x0A00, mutta muistamme, että pinomme on pre-dekrementaalinen. Siksi ensin osoitetta pienennetään kahdella (0x0A00 - 2 = 0x09FE) ja data kirjoitetaan soluun vastaanotetun osoitteen kanssa.
Muisti näytti alun perin tältä:
PUSH-komennon suorittamisen jälkeen (muutokset korostettu punaisella):
Data on siis tallennettu.
Tarkistetaan, onko tämä totta, suorittamalla kaksi siirtokomentoa (mov). Ensin vastaanotamme tiedot solusta 0x0A00 ja kirjoitamme sen rekisteriin R5 ja sitten kirjoitamme tiedot solusta 0x09FE rekisteriin R6.
Tämän jälkeen rekisterit sisältävät seuraavat tiedot:
POP-komentoja suoritettaessa pinon yläreunaa kasvatetaan 2:lla jokaisella komennolla, ja rekistereiden R8-10 tiedot ovat vastaavasti 0x0000, 0x9250 ja 0x0123.
Kun lisää dataa lisätään, muisti (joka sisältää edelleen pinosta poksatut tiedot) täyttyy uusilla arvoilla.
Voit havainnollistaa pinon kanssa työskentelemistä näin (vasemmalta oikealle):
Aluksi pinon osoite oli 0x0A00, siihen tallennettiin 0000 Kun PUSH suoritettiin, alla olevasta solusta (osoitteella 0x09FE) tuli pinon yläosa ja siihen kirjoitettiin tiedot. Jokaisen seuraavan komennon kohdalla yläosa sijaitsee alempana muistissa.
POP-komentoa suoritettaessa kuva on käänteinen.
Odotan kysymyksiäsi kommenteissa.
Hei, olen toisen vuoden opiskelija teknillisessä yliopistossa. Puuttuani muutamasta ohjelmointitunnista terveydellisistä syistä jouduin ymmärtämään puutteita sellaisista aiheista kuin Stack ja Queue. Yrityksen ja erehdyksen kautta muutaman päivän kuluttua sain vihdoin selville, mitä se oli ja minkä kanssa se syötiin. Jotta ymmärtämisesi ei vie niin paljon aikaa, tässä artikkelissa puhun siitä, mikä "pino" on, miten ja millä esimerkeillä ymmärsin, mikä se on. Jos pidät siitä, kirjoitan toisen osan, joka koskettaa sellaista käsitettä kuin "jono"
Teoria
Wikipediassa pinon määritelmä on:
Pino (englanniksi pino - pino; lue pino) on abstrakti tietotyyppi, joka on lista elementeistä, jotka on järjestetty LIFO-periaatteen mukaisesti (englanniksi last in - first out, "last in - first out").
Tarpeeksi täydellinen määritelmä, mutta se voi olla hieman vaikea ymmärtää aloittelijoille.
Siksi ensimmäinen asia, johon haluaisin keskittyä, on pinon esittäminen elämän asioiden muodossa. Ensimmäinen tulkinta, joka tuli mieleeni, oli kirjapinon muodossa, jossa ylin kirja on ylin.
Itse asiassa pino voidaan esittää pinona mitä tahansa esineitä, olipa se pino arkkeja, muistikirjoja, paitoja jne., mutta mielestäni kirjojen esimerkki on optimaalinen.
Joten mistä pino koostuu?
Pino koostuu soluista (esimerkissä nämä ovat kirjoja), jotka esitetään rakenteena, joka sisältää jonkin verran dataa ja osoittimen tämän rakenteen tyyppiin seuraava elementti.
Vaikea? Ei hätää, selvitetään se.
Tämä kuva näyttää kaaviomaisesti pinon. "Data/*seuraava" -muodon lohko on solumme. *seuraava, kuten näemme, osoittaa seuraavaan elementtiin, toisin sanoen *seuraava-osoitin tallentaa seuraavan solun osoitteen. *TOP-osoitin osoittaa pinon yläosaan, eli se tallentaa osoitteensa.
Teoria on valmis, siirrytään käytäntöön.
Harjoitella
Ensin meidän on luotava rakenne, joka on "solumme"
C++ koodi
struct comp ( //Rakenne nimeltä comp (sanakomponentista) int Data; //Jotkut tiedot (voivat olla mitä tahansa, voit esimerkiksi kirjoittaa int-avaimen; char Data; voit myös lisätä muita tietoja) comp *seuraava;/ /Comp tyyppi osoitin seuraavaan elementtiin);
Aloittelijat eivät ehkä ymmärrä, miksi osoitin on tyyppiä comp tai tarkemmin sanottuna comp-rakennetyyppinen osoitin. Selitän, jotta *next-osoitin tallentaa comp-rakenteen, sen on ilmoitettava tämän rakenteen tyyppi. Toisin sanoen ilmoittaa, mitä osoitin tallentaa.
Kun "solu" on asetettu, siirrytään toimintojen luomiseen.
Toiminnot
Toiminto "pinon" luomiseksi/elementin lisäämiseksi "pinoon"
Kun lisäät elementin, meillä on kaksi tilannetta:
- Pino on tyhjä ja se on luotava
- Pino on jo olemassa, ja sinun tarvitsee vain lisätä siihen uusi elementti
C++ koodi
void s_push(comp **top, int D) ( //funktio tyyppiä void (ei palauta mitään), joka vie osoittimen pinon alkuun ja muuttujan, joka kirjoitetaan soluun comp *q; //Luo uusi osoitin q rakennetyyppiä comp Pohjimmiltaan tämä on uusi elementti q = new comp() //varaa muistia uudelle elementille q->Data = D elementti if (top == NULL) ( //Jos kärkeä ei ole, eli pino on tyhjä *top = q; //pinon yläosasta tulee uusi elementti) else //jos pino ei ole tyhjä ( q->next = *top; //Vedämme yhteyden uudesta elementistä alkuun. Eli laitamme kirjan pinon päälle. *top = q; //Meritä, että yläosa on nyt uusi elementti ) )
Katsotaanpa sitä hieman tarkemmin.
Ensinnäkin, miksi funktio hyväksyy **topin, eli osoittimen osoittimeen, jätän tämän kysymyksen tarkastelun myöhempään, jotta se olisi sinulle selvempi. Toiseksi, puhutaanpa tarkemmin q->seuraava = *ylä ja siitä mitä se tarkoittaa ->
.
-> tarkoittaa, että karkeasti sanottuna menemme rakenteeseemme ja otamme sieltä osan tästä rakenteesta. Linjassa q->seuraava = *ylä Otamme osoittimen seuraavaan elementtiin *seuraavassa solussamme ja korvaamme sen osoittimella, joka osoittaa pinon alkuun *top. Toisin sanoen muodostamme yhteyden uudesta elementistä pinon yläosaan. Tässä ei ole mitään monimutkaista, kaikki on kuin kirjoissa. Asetamme uuden kirjan täsmälleen pinon päälle, eli vedämme yhteyden uudesta kirjasta kirjapinon yläosaan. Sen jälkeen Uusi kirja tulee automaattisesti ylimmäksi, koska pino ei ole kirjojen pino, meidän on ilmoitettava, että uusi elementti on ylin, tätä varten kirjoitamme: *ylä = q;.
Toiminto elementin poistamiseksi "pinosta" tietojen perusteella
Tämä toiminto poistaa elementin pinosta, jos solun Datan lukumäärä (q->Data) on sama kuin itse määrittämämme numero.
Vaihtoehdot voivat olla seuraavat:
- Solu, joka meidän on poistettava, on pinon yläosa
- Poistettava solu on lopussa tai kahden solun välissä
C++ koodi
void s_delete_key(comp **top, int N) (//toiminto, joka ottaa yläosan ja poistettavan luvun comp *q = *top; //luo comp-tyyppinen osoitin ja rinnasta (laita) se alkuun pinosta comp *prev = NULL;//luomme osoittimen edelliseen elementtiin, alusta alkaen se on tyhjä, kun taas (q != NULL) (//kun osoitin q ei ole tyhjä, suoritamme koodin silmukassa, jos se on edelleen tyhjä silmukka päättyy if (q-> Data == N) (//jos elementin Data on yhtä suuri kuin numero, joka meidän on poistettava if (q == *top) ( //jos tällainen osoitin on yhtä suuri kuin alkuun, niin on elementti, joka täytyy poistaa - top *top = q- >seuraava;//siirrä kärki seuraavaan elementtiin free(q);//clear solu q->Data = NULL //Seuraavaksi virheiden välttämiseksi nollaamme muuttujat etäsolussa, koska joissakin kääntäjissä etäsolussa on ei-NULL-muuttujien arvoja, mutta kirjaimellisesti "Muistin lukeminen on mahdotonta" tai numeroita; “-2738568384” tai muut, kääntäjästä riippuen q->next = NULL ) else//jos elementti on viimeinen tai kahden muun elementin välissä ( prev->next = q ->next;//Piirrä yhteys edellisestä elementistä seuraavaan free(q);//tyhjennä solu q->Data = NULL;//nollaa muuttujat q->next = NULL; ) ) // jos elementin Data EI ole yhtä suuri kuin numero meidän täytyy poistaa prev = q; //muista nykyinen solu edellisenä q = q->seuraava;//siirrä osoitin q seuraavaan elementtiin ) )
Osoitin q sisään tässä tapauksessa sillä on sama rooli kuin osoitin muistiossa, se pyörii koko pinon ympäri, kunnes siitä tulee NULL( while(q != NULL)), toisin sanoen, kunnes pino loppuu.
varten parempi ymmärrys Kun poistat elementin, vedetään analogia jo tutun kirjapinon kanssa. Jos meidän on poistettava kirja ylhäältä, poistamme sen, ja sen alla olevasta kirjasta tulee ylin. Se on sama täällä, vain alussa meidän on päätettävä, että seuraavasta elementistä tulee huippu *ylä = q->seuraava; ja vasta sitten poista elementti vapaa(q);
Jos poistettava kirja on kahden kirjan välissä tai kirjan ja pöydän välissä, edellinen kirja putoaa seuraavan päälle tai pöydälle. Kuten jo ymmärsimme, kirjamme on solu, ja taulukko osoittautuu NULLiksi, eli seuraavaa elementtiä ei ole. Se käy samalla tavalla kuin kirjoissa, määritämme, että edellinen solu yhdistetään seuraavaan edellinen->seuraava = q->seuraava;, se kannattaa huomioida edellinen->seuraava voi olla yhtä suuri kuin solu tai nolla, jos q->seuraava = NULL, eli solua ei ole (kirja makaa pöydällä), sen jälkeen tyhjennämme solun ilmainen (q).
On myös syytä huomata, että jos et tämä yhteys, poistetun solun jälkeen oleva soluosa muuttuu käyttökelvottomaksi, koska juuri yhteys, joka yhdistää solun toiseen, katoaa ja tämä osa yksinkertaisesti katoaa muistista.
Pinottava näyttötoiminto
Yksinkertaisin toiminto:
C++ koodi
void s_print(comp *top) ( //hyväksyy osoittimen pinon alkuun comp *q = top; //asettaa q alkuun while (q) ( //kunhan q ei ole tyhjä (while(q ) on sama kuin while(q != NULL )) printf_s("%i", q->Data);//näytä pinosolun tiedot q = q->seuraava;//siirrä sen näyttämisen jälkeen q kohtaan seuraava elementti (solu) )
Tässä mielestäni kaikki on selvää, haluan vain sanoa, että q tulee nähdä liukusäätimenä, se kulkee kaikkien solujen yli ylhäältä, missä asetamme sen alussa: *q = yläosa;, viimeiseen elementtiin.
Päätoiminto
Okei, olemme kirjoittaneet pääfunktiot pinon kanssa työskentelyyn ja kutsuneet niitä.
Katsotaanpa koodia:
C++ koodi
void main() ( comp *top = NULL; //ohjelman alussa meillä ei ole jonoa, joten ei ole kärkeä, annamme sen NULL arvo//Seuraavaksi alamme lisätä numeroita 1 - 5 pinoon s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //pinon funktioiden suorittamisen jälkeen meillä on 54321 s_print(top);//print s_delete_key(&top, 4); //Sitten poistamme 4, pinon lopussa on 5321 printf_s("\n");//siirrä uusi rivi s_print(top);//tulostusjärjestelmä("tauko");//tauko)
Palataan siihen, miksi välitimme osoittimen funktion kärkiosoittimelle. Tosiasia on, että jos ottaisimme funktioon vain osoittimen kärkeen, niin "pino" luotaisiin ja muutetaan vain pääfunktion funktion sisällä. Ohjaamalla osoittimen osoittimeen muutamme pääfunktion *top vertexin. Osoittautuu, että jos funktio muuttaa pinoa, sinun on välitettävä sille kärkipiste osoittimella, kuten teimme funktiossa s_push, s_delete_key. S_print-funktiossa "Stack" ei saisi muuttua, joten siirrämme yksinkertaisesti osoittimen alkuun.
Voit käyttää myös numeroiden 1,2,3,4,5 sijasta tyyppisiä muuttujia int.
Johtopäätös
Koko ohjelmakoodi:
C++ koodi
#sisältää
Toteutustulos
Koska elementtejä lisätään jatkuvasti pinon yläosaan, elementit näytetään käänteisessä järjestyksessä.
Lopuksi haluan kiittää teitä siitä, että käytit aikaa artikkelini kirjoittamiseen, toivon sitä todella tätä materiaalia auttoi joitain aloittelevia ohjelmoijia ymmärtämään, mikä pino on, kuinka sitä käytetään, ja tulevaisuudessa heillä ei enää ole ongelmia. Kirjoita mielipiteesi kommentteihin sekä kuinka voin parantaa artikkeleitani tulevaisuudessa. Kiitos huomiostasi.
