Johdanto
Jono on kokoelma kohteita, joissa ensimmäisen luetteloon lisätyn kohteen on oltava ensimmäinen poistettava kohde seuraavaksi. Joten kun esineitä lisätään kokoelmaan, sen koko kasvaa, eli sen pituus kasvaa. Aina kun jokin kohde on poistettava, se on lisättävä ensimmäisenä. Jos kohteita poistetaan jatkuvasti, seuraavaksi poistettu on toinen kohde; kolmas poistetaan jälkeenpäin ja niin edelleen.
Kun alkuperäisen luettelon ensimmäinen kohde on poistettu, toisesta tulee ensimmäinen kohde. Kun toinen kohde on poistettu, kolmannesta tulee ensimmäinen kohde ja niin edelleen.
Hyvä tosielämän esimerkki jonosta on se, kun ihmiset jonottavat odottamaan palvelua tai hyvää. Ensimmäinen henkilö tarjoillaan ensin ennen viimeistä. Kuitenkin tässä opetusohjelmassa puhuttu jono on ohjelmistojono, kuten C ++: ssa on suunniteltu.
FIFO
FIFO tarkoittaa First-In, First-Out. Se on toinen tapa arvioida jonoa. Tämä tarkoittaa sitä, että ensimmäinen luetteloon tuleva kohde on ensimmäinen poistettava kohde aina, kun poistaminen tapahtuu. Luettelon alkua kutsutaan pääksi tai eteen; luettelon loppua kutsutaan seläksi tai hännäksi.
Olennaiset toiminnot
Ohjelmistojonossa on oltava vähintään seuraavat toiminnot:
työntää
Tämä toiminto lisää uuden elementin jonon taakse. Tätä operaatiota kutsutaan virallisesti enqueueksi.
siirtää
Tämä toiminto poistaa jonon ensimmäisen elementin ja toisesta elementistä tulee uusi ensimmäinen elementti. Tätä operaatiota kutsutaan virallisesti dequeueksi. Sitä kutsutaan popiksi C ++: ssa.
Tässä artikkelissa kerrotaan, miten C ++ -jonon tietorakennetta käytetään. Sinun pitäisi tietää C ++ -osoittimet ja viittaukset ymmärtääksesi tämän artikkelin loput.
Luokka ja esineet
Luokka on joukko muuttujia ja funktioita, jotka toimivat yhdessä ja joissa muuttujille ei ole määritetty arvoja. Kun muuttujille on määritetty arvot, luokasta tulee objekti. Samalle luokalle annetut eri arvot johtavat eri objekteihin; eli eri objektit ovat sama luokka, jolla on erilaiset arvot. Objektin luominen luokasta sanotaan objektin havainnollistamiseksi.
Nimi, jono, on luokka. Jonoluokasta luodulla objektilla on ohjelmoijan valitsema nimi.
Luokkaan kuuluva funktio tarvitaan objektin luontiin luokasta. C ++: ssa kyseisellä funktiolla on sama nimi kuin luokan nimellä. Luokasta luoduilla (näytteillä) olevilla objekteilla on eri nimet, jotka ohjelmoija on antanut heille.
Objektin luominen luokasta tarkoittaa objektin rakentamista; se tarkoittaa myös hetkellistämistä.
C ++ -ohjelma, joka käyttää jonoluokkaa, alkaa seuraavilla riveillä tiedoston yläosassa:
#sisältää#sisältää
käyttämällä nimiavaruuden std;
Ensimmäinen rivi on tulo/lähtö. Toinen rivi on antaa ohjelman käyttää kaikkia jonoluokan ominaisuuksia. Kolmannella rivillä ohjelma voi käyttää nimiä normaalissa nimitilassa.
Toiminnon ylikuormitus
Kun kahdella tai useammalla eri funktion allekirjoituksella on sama nimi, sen sanotaan olevan ylikuormitettu. Kun yksi funktio kutsutaan, argumenttien määrä ja tyyppi määrittävät, mikä funktio todella suoritetaan.
Rakentaminen
jonottaa<tyyppi>nimi()Seuraava ilmoitus luo jonon nimeltä, jono tyyppi int.
jonottaa<int>että;Jono on tyhjä. Ilmoitus alkaa varatulla sanalla jono ja sen jälkeen kulmat hakasulkeilla tietotyypin kanssa. Sitten sinulla on ohjelmoijan etunimi jonolle.
Rakentaminen alustuslistan avulla
Seuraava määritelmä näyttää jonon luomisen alustusluettelolla:
jonottaa<kellua>että({1.1, 2.2, 3.3, 4.4});Jonon tuhoaminen
Jos haluat tuhota jonon, anna sen vain mennä soveltamisalan ulkopuolelle.
Jonon elementtien käyttö
push (arvo)
Jono on First-In-First-Out -luettelo. Joten jokainen arvo lisätään takaa. Seuraava koodisegmentti luo tyhjän jonon, jonka jälkeen viisi float -arvoa lisätään takaa:
jonottaa<kellua>että;että.työntää(1.1);
että.työntää(2.2);
että.työntää(3.3);
että.työntää(4.4);
että.työntää(5.5);
koko () const
Tämä palauttaa jonon elementtien määrän. Seuraava koodi havainnollistaa:
jonottaa<kellua>että;että.työntää(1.1);että.työntää(2.2);että.työntää(3.3);että.työntää(4.4);että.työntää(5.5);
kustannus<<että.koko() << '' n'';
Lähtö on 5.
edestä ()
Tämä palauttaa viittauksen jonon ensimmäiseen elementtiin poistamatta elementtiä. Seuraavan koodin tulos on 1.1.
jonottaa<kellua>että;että.työntää(1.1);että.työntää(2.2);että.työntää(3.3);että.työntää(4.4);että.työntää(5.5);
kustannus<<että.edessä() << '' n'';
Elementtiä ei poisteta jonosta.
edessä () const
Kun jonorakennetta edeltää const, lauseke front () const suoritetaan front (): n sijasta. Sitä käytetään esimerkiksi seuraavassa koodissa.
constjonottaa<kellua>että({1.1, 2.2, 3.3, 4.4, 5.5});kustannus<<että.edessä() << '' n'';
Jatkuva viite palautetaan. Elementtiä ei poisteta vektorista. Jonoelementtejä ei voi muuttaa.
takaisin()
Tämä palauttaa viittauksen jonon viimeiseen elementtiin poistamatta elementtiä. Seuraavan koodin lähtö on 5.5.
jonottaa<kellua>että;että.työntää(1.1);että.työntää(2.2);että.työntää(3.3);että.työntää(4.4);että.työntää(5.5);
kustannus<<että.takaisin() << '' n'';
takaisin () const
Kun jonorakennetta edeltää const, lauseke back () const suoritetaan back (): n sijasta. Sitä käytetään esimerkiksi seuraavassa koodissa.
constjonottaa<kellua>että({1.1, 2.2, 3.3, 4.4, 5.5});kustannus<<että.takaisin() << '' n'';
Jatkuva viite palautetaan. Elementtiä ei poisteta jonosta. Jonojärjestelmän edellisen konstin avulla jonon elementtejä ei voi muuttaa.
Jonon kapasiteetti
koko () const
- Katso edellä
tyhjä () const
Tämä palauttaa arvon 1 tosi, jos jonossa ei ole elementtejä, tai 0, jos epätosi, jos jono on tyhjä. Seuraava koodi havainnollistaa tätä:
jonottaa<kellua>että 1({1.1, 2.2, 3.3, 4.4, 5.5});kustannus<<että 1.tyhjä() << '' n'';
jonottaa<kellua>että2;
kustannus<<että2.tyhjä() << '' n'';
Lähtö on:
01
Jononmuokkaajat
pop ()
Jono on FIFO, joten kaikki poistettavat elementit on poistettava jonon yläosasta (päästä). Tämä jäsentoiminto poistaa ensimmäisen elementin palauttamatta sitä. Seuraava koodi havainnollistaa tätä:
jonottaa<kellua>että({1.1, 2.2, 3.3, 4.4, 5.5});kustannus<<että.edessä() << '' n'';
että.pop-();
kustannus<<että.koko() << '' n'';
Lähtö on:
1.14
a. vaihto (b)
Kaksi jonoa voidaan vaihtaa, kuten tässä koodisegmentissä on esitetty:
jonottaa<kellua>että 1({1.1, 2.2, 3.3, 4.4, 5.5});jonottaa<kellua>että2({10, kaksikymmentä});
että 1.vaihtaa(että2);
kustannus<< 'Ensimmäinen elementti ja que1: n koko:
''<<että 1.edessä() <<','<<että 1.koko() << '' n'';
kustannus<< 'Ensimmäinen elementti ja que2 -koko'<<
että2.edessä() <<','<<että2.koko() << '' n'';
Lähtö on:
Ensimmäinen elementti ja que1: 10, 2 koko
Ensimmäinen elementti ja que2: koko: 1.1, 5
Huomaa, että jonon pituutta lisätään tarvittaessa. Myös arvot, joilla ei ollut korvauksia, korvataan jollakin oletusarvolla. Tietotyyppien on oltava samaa tyyppiä.
Tasa -arvo- ja suhdeoperaattorit jonoille
C ++: n tavallisissa merkeissä nousevassa järjestyksessä numerot tulevat ennen isoja kirjaimia ja pieniä kirjaimia. Välihahmo tulee ennen nollaa ja ne kaikki.
Tasa -arvo -operaattorit
Palauttaa arvon 1 tosi ja 0 epätosi.
== operaattori
Palauttaa 1, jos kahden jonon koko on sama ja vastaavat elementit ovat yhtä suuret; muuten se palauttaa arvon 0. Esimerkki:
jonottaa<const hiiltyä*>että 1({'ystävällinen', 'jotain muuta'});jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1==että2;
kustannus<<yhdellä<< '' n'';
Lähtö on: 0.
The! = Käyttäjä
- päinvastainen kuin edellä. Esimerkki:
jonottaa<const hiiltyä*>että 1({'ystävällinen', 'jotain muuta'});jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1! =että2;
kustannus<<yhdellä<< '' n'';
Lähtö on: 1.
Suhteelliset toimijat
Palauttaa arvon 1 tosi ja 0 epätosi.
The
Palauttaa arvon 1, jos ensimmäinen jono on toisen jonon ensimmäinen osajoukko, jossa kahden saman osan elementit ovat samat ja samassa järjestyksessä. Jos molemmat jonot ovat samankokoisia tai erikokoisia ja siirtyvät vasemmalta oikealle, ensimmäisessä jonossa on elementti, joka on pienempi kuin toisen jonon vastaava elementti, 1 palautetaan silti. Muuten 0 palautetaan. Esimerkki:
jonottaa<const hiiltyä*>että 1({'ystävällinen', 'jotain muuta'});jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1<että2;
kustannus<<yhdellä<< '' n'';
Lähtö on 1. > Käyttäjä - päinvastainen kuin edellä. Esimerkki: Lähtö: 0 The<= Operator - sama kuin Lähtö: 1 > = Käyttäjä - päinvastainen kuin edellä. Esimerkki: Lähtö: 0 Arvo on tietotyypille, kuten luotu objekti luokalle. Jonorakenne voi myös hyväksyä luokan tietotyypiksi. Seuraava ohjelma havainnollistaa tätä: Lähtö on 5. Jono -luetteloa kutsutaan teknisesti linkitetyksi luetteloksi. Jonossa on kahdenlaisia linkitettyjä luetteloita: yksittäin linkitetty luettelo ja kaksinkertaisesti linkitetty luettelo. Yksin linkitetty luetteloelementti voidaan toteuttaa kahden jäsenen rakenteella. Toinen jäsen pitää osoitinta seuraavaan elementtiin ja toinen jäsen datumiin (yksikkö datalle). Kaksinkertaisesti linkitetty luetteloelementti voidaan toteuttaa kolmen jäsenen rakenteella. Keskimmäinen osa pitää nollapistettä, kun taas ensimmäinen ja kolmas jäsen pitävät osoittimia viereisiin elementteihinsä. Jono on ensimmäinen ensimmäisessä-ulos-tietorakenne. Tietojenkäsittelyssä on tilanteita, kun tiedot saapuvat jonon muodossa, mikä edellyttää ensimmäistä ensimmäisessä -käyttäytymistä. Tietokoneen resurssi on mikä tahansa fyysinen tai virtuaalinen osa, jonka saatavuus on rajoitettu. Niitä ovat suoritin, näytönohjain, kiintolevy ja muisti. Tällaisen resurssin jakaminen vaatii jonon. Tietokoneen oheislaitteiden on keskeytettävä tietokone ajoittain. Keskeytykset on käsiteltävä samalla tavalla kuin ne saapuivat. Tämä vaatii jonon. Jonoa voidaan käyttää esimerkiksi työn sovellustiedostojen hallintaan, jos tiedostot on tallennettu tietokoneeseen. Jono on luettelotietorakenne, joka on joko yksittäisesti linkitetty tai kaksinkertaisesti linkitetty luettelo. Yleensä ensimmäinen elementti, joka tulee luetteloon, on ensimmäinen elementti, joka tulee ulos. C ++ tarjoaa jonotietorakenteen vakiokirjastoonsa. Tässä rakenteessa käytettävissä olevat jäsentoimintojen ja operaattorien luokat ovat jonorakentaminen, jonoelementtien käyttöoikeus, jonokapasiteetti, jononmuokkaajat ja ylikuormitetut operaattorit. Jonkin tietorakenteen on sisällettävä ainakin push () - ja pop () -jäsentoiminnot. push () tarkoittaa uuden elementin lähettämistä jonon taakse; ja pop () tarkoittaa jonon edessä olevan elementin poistamista. Valitettavasti C ++: ssa nämä toiminnot eivät palauta työnnettyä tai ponnahdettua arvoa. Joten tietääksesi viimeisen elementin ennen työntämistä, on käytettävä ylimääräistä takaisin () -toimintoa; ja tietää ensimmäinen elementti ennen popping, extra front () -toimintoa on käytettävä. Arvo on tietotyypille, kuten luotu objekti luokalle. Niinpä tiettyä luokkaa voidaan käyttää tietotyyppinä jonomallin välitykseen. Luokan eri kohteista tulee samanlaisia kuin luokan eri arvot. Jonossa on sovelluksia tietokoneessa. Sitä voidaan käyttää esimerkiksi työn sovellustiedostojen hallintaan, jos tiedostot on tallennettu tietokoneeseen. Chrys
jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1>että2;
kustannus<<yhdellä<< '' n'';
jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1<=että2;
kustannus<<yhdellä<< '' n'';
jonottaa<const hiiltyä*>että2({'ilkeä'});
intyhdellä=että 1> =että2;
kustannus<<yhdellä<< '' n''; Luokka ja sen välittävät objektit
#sisältää
käyttämällä nimiavaruuden std;
luokka TheCla
{
julkinen:
intyhdellä;
staattinen hiiltyäch;
mitätöntoiminto(hiiltyäei, const hiiltyä *s)
{
kustannus<< 'Siellä on ' <<yhdellä<< 'arvokkaita kirjoja' <<ei<<s<< ' kaupassa.' << '' n'';
}
staattinen mitätönhauskaa(hiiltyäch)
{
jos (ch== '')
kustannus<< '' Virallinen staattinen jäsentoiminto '' << '' n'';
}
};
inttärkein()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
jonottaa<TheCla>että;
että.työntää(obj1);että.työntää(obj2);että.työntää(obj3);että.työntää(obj4);että.työntää(obj5);
kustannus<<että.koko() << '' n'';
palata 0;
} Linkitetty luettelo
Jonon sovellukset
Tietokoneresurssien jakaminen
Keskeytysten käsittely
Hallinnoi tietoja.
Johtopäätös