Kuinka käyttää C ++ Priority_queue -järjestelmää?

How Use C Priority_queue

C ++: ssa jono on luettelotietorakenne, jossa ensimmäinen luetteloon lisättävä elementti on ensimmäinen poistettava elementti poistamisen yhteydessä. Prioriteettijono C ++: ssa on samanlainen, mutta siinä on jonkin verran järjestystä; se elementti, jolla on suurin arvo, poistetaan ensin. Prioriteettijono voidaan edelleen määrittää siten, että se on elementti, jolla on vähiten arvoa, joka poistetaan ensin. Jonossa on oltava vähintään työntää() toiminto ja pop () toiminto. The työntää() toiminto lisää uuden elementin taakse. Normaalia jonoa varten pop () -toiminto poistaa ensimmäisen elementin, joka on koskaan työnnetty sisään. Prioriteettijonoa varten pop () -toiminto poistaa korkeimman prioriteetin elementin, joka voi olla suurin tai pienin tilausmallista riippuen.

Jotta C ++ -prioriteetinjonoa voidaan käyttää, ohjelman pitäisi alkaa koodilla, joka on seuraava:



#sisältää
#sisältää
käyttämällä nimiavaruustuntia;

Se sisältää ohjelmaan jonokirjaston.



Jatkaakseen lukemista lukijalla olisi pitänyt olla perustiedot C ++: sta.



Artikkelin sisältö

Perusrakenne

Tietorakenne on rakennettava ensin, ennen kuin sitä voidaan käyttää. Rakentaminen tarkoittaa tässä objektin näyttämistä kirjaston jonoluokasta. Tämän jälkeen jono -objektilla on oltava ohjelmoijan antama nimi. Yksinkertaisin syntaksi prioriteettijonon luomiseen on:

prioriteetti_jono<tyyppi>queueName;

Tällä syntaksilla suurin arvo poistetaan ensin. Esimerkki hetkellisyydestä on:

prioriteetti_jono<int>s;

tai



prioriteetti_jono<hiiltyä>s;

Vektori ja dekki ovat kaksi datarakennetta C ++: ssa. Prioriteetti_jono voidaan luoda jollakin niistä. Syntaksi prioriteettijonon luomiseksi vektorirakenteesta on:

prioriteetti_jono<tyyppi, vektori<samaa tyyppiä>, vertailla>s;

Esimerkki tästä esittelystä on:

prioriteetti_jono<int, vektori<int>, vähemmän<int> >s;

Huomaa väli> ja> ilmoituksen lopussa. Näin vältetään sekaannus >>. Oletusarvoinen vertailukoodi on pienempi, eli suurin ja ei välttämättä ensimmäinen arvo poistetaan ensin. Joten luomislauseke voidaan yksinkertaisesti kirjoittaa seuraavasti:

prioriteetti_jono<int, vektori<int> >s;

Jos pienin arvo poistetaan ensin, lausuman on oltava:

prioriteetti_jono<int, vektori<int>, suurempi<int> >s;

Tärkeitä jäsentoimintoja

Push () -toiminto
Tämä funktio työntää arvon, joka on sen argumentti, prioriteettijonoon. Se palauttaa tyhjyyden. Seuraava koodi havainnollistaa tätä:

prioriteetti_jono<int>s;

s.työntää(10);
s.työntää(30);
s.työntää(kaksikymmentä);
s.työntää(viisikymmentä);
s.työntää(40);

Tämä prioriteettijono on saanut 5 kokonaislukua, jotka ovat luokkaa 10, 30, 20, 50, 40. Jos kaikki nämä elementit poistetaan prioriteettijonosta, ne tulevat ulos luokassa 50, 40, 30, 20, 10.

Pop () -toiminto
Tämä toiminto poistaa prioriteettijonosta arvon, jolla on korkein prioriteetti. Jos vertailukoodi on suurempi, se poistaa elementin, jolla on pienin arvo. Jos se kutsutaan uudelleen, se poistaa seuraavan elementin, jolla on pienin lopun arvo; uudelleen, se poistaa seuraavan pienimmän nykyisen arvon ja niin edelleen. Se palauttaa tyhjyyden. Seuraava koodi havainnollistaa tätä:

prioriteetti_jono<hiiltyä, vektori<hiiltyä>, suurempi<int> >s;
s.työntää('');s.työntää('c');s.työntää('b');s.työntää('Ja');s.työntää('d');

Huomaa, että jäsenfunktion kutsuminen edellyttää, että objektin nimen jälkeen on oltava piste ja sitten funktio.

Ylin () -toiminto
The pop () -toiminto poistaa seuraavan korkeimman prioriteetin arvon, mutta ei palauta sitä, kuten pop () on tyhjä funktio. Käytä alkuun () -toiminto tietääksesi korkeimman prioriteetin arvon, joka on poistettava seuraavaksi. The alkuun () -toiminto palauttaa kopion prioriteetin_jonon korkeimman prioriteetin arvosta. Seuraava koodi, jossa seuraava korkeimman prioriteetin arvo on pienin arvo, havainnollistaa tätä

prioriteetti_jono<hiiltyä, vektori<hiiltyä>, suurempi<int> >s;
s.työntää('');s.työntää('c');s.työntää('b');s.työntää('Ja');s.työntää('d');
hiiltyäch1=s.alkuun();s.pop-();
hiiltyäch2=s.alkuun();s.pop-();
hiiltyäch3=s.alkuun();s.pop-();
hiiltyäch4=s.alkuun();s.pop-();
hiiltyäch5=s.alkuun();s.pop-();

kustannus<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<'' n'';

Tulos on 'a' 'b' 'c' 'd' 'e'.

Tyhjä () -toiminto
Jos ohjelmoija käyttää alkuun () toiminto tyhjällä prioriteetti_jonolla, onnistuneen kääntämisen jälkeen hän saa virheilmoituksen, kuten:

Segmentointivika(ydin polkumyynnillä)

Tarkista siis aina, onko prioriteettijono tyhjä, ennen kuin käytät alkuun () toiminto. The tyhjä() jäsenfunktio palauttaa bool -arvon, tosi, jos jono on tyhjä, ja epätosi, jos jono ei ole tyhjä. Seuraava koodi havainnollistaa tätä:

prioriteetti_jono<int>s;
inti1= 10; inti2= 30; inti3= kaksikymmentä; inti4= viisikymmentä; inti5= 40;
s.työntää(i1);s.työntää(i2);s.työntää(i3);s.työntää(i4);s.työntää(i5);

sillä aikaa(!s.tyhjä())
{
kustannus <<s.alkuun() << '';
s.pop-();
}
kustannus << '' n'';

Muut tärkeät jonotoiminnot

Koko () -toiminto
Tämä toiminto palauttaa prioriteettijonon pituuden, kuten seuraava koodi havainnollistaa:

prioriteetti_jono<int>s;
inti1= 10; inti2= 30; inti3= kaksikymmentä; inti4= viisikymmentä; inti5= 40;
s.työntää(i1);s.työntää(i2);s.työntää(i3);s.työntää(i4);s.työntää(i5);

intlen=s.koko();
kustannus <<len<< '' n'';

Lähtö on 5.

Vaihto () -toiminto
Jos kaksi prioriteetti_jonoa ovat samaa tyyppiä ja kokoa, tämä toiminto voi vaihtaa ne, kuten seuraava koodi osoittaa:

prioriteetti_jono<int>pq1;
inti1= 10; inti2= 30; inti3= kaksikymmentä; inti4= viisikymmentä; inti5= 40;
pq1.työntää(i1);pq1.työntää(i2);pq1.työntää(i3);pq1.työntää(i4);pq1.työntää(i5);

prioriteetti_jono<int>pqA;
intse 1= 1; intse 2= 3; intse 3= 2; intse 4= 5; intse 5= 4;
pqA.työntää(se 1);pqA.työntää(se 2);pqA.työntää(se 3);pqA.työntää(se 4);pqA.työntää(se 5);

pq1.vaihtaa(pqA);

sillä aikaa(!pq1.tyhjä())
{
kustannus <<pq1.alkuun() << '';
pq1.pop-();
} kustannus<<'' n'';

sillä aikaa(!pqA.tyhjä())
{
kustannus <<pqA.alkuun() << '';
pqA.pop-();
} kustannus<<'' n'';

Lähtö on:

& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10

Emplace () Fuction
The emplace () toiminto on samanlainen kuin push -toiminto. Seuraava koodi havainnollistaa tätä:

prioriteetti_jono<int>pq1;
inti1= 10; inti2= 30; inti3= kaksikymmentä; inti4= viisikymmentä; inti5= 40;
pq1.sijoittaa(i1);pq1.sijoittaa(i2);pq1.sijoittaa(i3);pq1.sijoittaa(i4);pq1.sijoittaa(i5);

sillä aikaa(!pq1.tyhjä())
{
kustannus <<pq1.alkuun() << '';
pq1.pop-();
} kustannus<<'' n'';

Lähtö on:

50 40 30 20 10

Merkkijonon tiedot

Merkkijonoja verrattaessa on käytettävä merkkijonoluokkaa eikä merkkijonojen kirjainten suoraa käyttöä, koska se vertaisi osoittimia eikä varsinaisia ​​merkkijonoja. Seuraava koodi näyttää merkkijonoluokan käytön:

#sisältää
prioriteetti_jono<merkkijono>pq1;
merkkijono s1=merkkijono('kynä'), s2=merkkijono('lyijykynä'), s3=merkkijono('tehtäväkirja'), s4=merkkijono('oppikirja'), s5=merkkijono('viivotin');

pq1.työntää(s1);pq1.työntää(s2);pq1.työntää(s3);pq1.työntää(s4);pq1.työntää(s5);
sillä aikaa(!pq1.tyhjä())
{
kustannus <<pq1.alkuun() << '';
pq1.pop-();
} kustannus<<'' n'';

Lähtö on:

& emsp; oppikirja & viivain & emsp; lyijykynä & emsp; kynä & emsp; harjoituskirja

Muut tärkeät jonorakenteet

Selkeä luominen vektorista
Prioriteettijono voidaan luoda nimenomaisesti vektorista, kuten seuraava koodi osoittaa:

#sisältää
vektori<int>vtr= {10,30,kaksikymmentä,viisikymmentä,40};

prioriteetti_jono<int>s(vtr.alkaa(), vtr.loppuun());

sillä aikaa(!s.tyhjä())
{
kustannus <<s.alkuun() << '';
s.pop-();
} kustannus<<'' n'';

Tulos on: 50 40 30 20 10. Tällä kertaa myös vektoriotsikko on sisällytettävä. Konstruktori -funktion argumentit ottavat vektorin alku- ja loppuosoittimet. Vektorin tietotyypin ja prioriteetin_jonon tietotyypin on oltava samat.

Jotta vähimmäisarvo olisi prioriteetti, rakentajan ilmoitus olisi:

prioriteetti_jono<int, vektori<int>, suurempi>int> >s(vtr.alkaa(), vtr.loppuun());

Selkeä luominen ryhmästä
Ensisijainen jono voidaan luoda suoraan taulukosta, kuten seuraava koodi osoittaa:

intarr[] = {10,30,kaksikymmentä,viisikymmentä,40};

prioriteetti_jono<int>s(arr, arr+5);

sillä aikaa(!s.tyhjä())
{
kustannus <<s.alkuun() << '';
s.pop-();
} kustannus<<'' n'';

Tulos on: 50 40 30 20 10. Konstruktori -funktion argumentit ottavat taulukon alku- ja loppukohdat. arr palauttaa aloitusosoittimen, arr+5 palauttaa osoittimen juuri matriisin ohi ja 5 on taulukon koko. Matriisin tietotyypin ja prioriteetti_jonon tietotyypin on oltava samat.

Jotta vähimmäisarvo olisi prioriteetti, rakentajan ilmoitus olisi:

prioriteetti_jono<int, vektori<int>, suurempi<int> >s(arr, arr+5);

Huomautus: C ++: ssa prioriteettijonoa kutsutaan itse asiassa sovittimeksi, ei vain säiliöksi.

Mukautettu vertailukoodi

Kaikkien prioriteettijonon arvojen nouseva tai laskeva ei ole ainoa prioriteettijonon vaihtoehto. Esimerkiksi luettelo 11 kokonaisluvusta suurimmalle kasalle on:

88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69

Suurin arvo on 88. Tämän jälkeen on kaksi numeroa: 86 ja 87, jotka ovat alle 88. Loput luvut ovat pienempiä kuin nämä kolme numeroa, mutta eivät oikeassa järjestyksessä. Luettelossa on kaksi tyhjää solua. Numerot 84 ja 82 ovat pienempiä kuin 86. Numerot 79 ja 74 ovat pienempiä kuin 87. Numerot 80 ja 81 ovat pienempiä kuin 84. Numerot 64 ja 69 ovat alle 79.

Numeroiden sijoitus noudattaa maksimi-kasan ehtoja-katso myöhemmin. Voidakseen tarjota tällaisen järjestelmän prioriteettijonolle ohjelmoijan on annettava oma vertailukoodinsa - katso myöhemmin.

Johtopäätös

C ++ -prioriteetin_jono on ensin ensimmäisessä-ulos -jono. Jäsentoiminto, työntää(), tuo jonoon uuden arvon. Jäsentoiminto, alkuun (), lukee jonon ylin arvo. Jäsentoiminto, pop (), poistaa palauttamatta jonon ylintä arvoa. Jäsentoiminto, tyhjä(), tarkistaa onko jono tyhjä. Prioriteettijono eroaa kuitenkin jonosta siinä, että se noudattaa jotakin prioriteettialgoritmia. Se voi olla suurin, ensimmäisestä viimeiseen tai vähiten, ensimmäisestä viimeiseen. Ehdot (algoritmi) voidaan myös ohjelmoida.