Kuidas kasutada funktsiooni C ++ Priority_queue?

How Use C Priority_queue

C ++ puhul on järjekord loendi andmestruktuur, kus esimene loendisse lisatav element on esimene eemaldatav element, kui eemaldamine toimub. C ++ prioriteedijärjekord on sarnane, kuid sellel on teatud järjekord; esmalt eemaldatakse kõige suurema väärtusega element. Prioriteedijärjekorda saab siiski konfigureerida nii, et see eemaldatakse kõigepealt väikseima väärtusega elemendist. Igas järjekorras peab olema vähemalt lükkama () funktsioon ja pop () funktsiooni. The lükkama () funktsioon lisab taha uue elemendi. Tavalise järjekorra jaoks on pop () funktsioon eemaldab esimese elemendi, mis kunagi sisse lükati. Prioriteedijärjekorra jaoks pop () funktsioon eemaldab kõrgeima prioriteediga elemendi, mis võib sõltuvalt tellimisskeemist olla suurim või väikseim.

C ++ prioriteedijärjekorra kasutamiseks peaks programm algama järgmise koodiga:



#kaasake
#kaasake
kasutades nimeruumtundi;

See sisaldab programmi järjekorraraamatukogu.



Lugemise jätkamiseks pidanuks lugejal olema C ++ põhiteadmised.



Artikli sisu

Põhikonstruktsioon

Enne andmestruktuuri kasutamist tuleb see kõigepealt üles ehitada. Ehitamine tähendab siin objekti kohesust raamatukogu järjekorraklassist. Järjekorra objektil peab siis olema programmeerija poolt antud nimi. Lihtsaim süntaks prioriteedijärjekorra loomiseks on järgmine:

prioriteedi_järjekord<tüüpi>queueName;

Selle süntaksi korral eemaldatakse kõigepealt suurim väärtus. Koondamise näide on järgmine:

prioriteedi_järjekord<int>pq;

või



prioriteedi_järjekord<süsi>pq;

Vektor ja dekk on C ++ kaks andmestruktuuri. Prioriteedijärjekorda saab luua kummagagi. Süntaks vektorstruktuurist prioriteedijärjekorra loomiseks on järgmine:

prioriteedi_järjekord<tüüp, vektor<sama tüüpi>, võrdlema>pq;

Selle näite näide on järgmine:

prioriteedi_järjekord<int, vektor<int>, vähem<int> >pq;

Märkige deklaratsiooni lõpus tühimik> ja> vahele. Selle eesmärk on vältida segadust >>. Vaikimisi võrdluskood on väiksem, see tähendab, et kõigepealt eemaldatakse suurim ja mitte tingimata esimene väärtus. Niisiis, loomise avalduse saab lihtsalt kirjutada järgmiselt:

prioriteedi_järjekord<int, vektor<int> >pq;

Kui kõigepealt tuleb eemaldada väikseim väärtus, peab avaldus olema järgmine:

prioriteedi_järjekord<int, vektor<int>, suurem<int> >pq;

Liikmete olulised funktsioonid

Funktsioon push ()
See funktsioon surub väärtuse, mis on selle argument, prioriteedijärjekorda. See tagastab tühimiku. Seda illustreerib järgmine kood:

prioriteedi_järjekord<int>pq;

pq.suruda(10);
pq.suruda(30);
pq.suruda(kakskümmend);
pq.suruda(viiskümmend);
pq.suruda(40);

See prioriteedi_järjekord on saanud 5 täisarvu väärtust suurusjärgus 10, 30, 20, 50, 40. Kui kõik need elemendid tuleb prioriteedijärjekorrast välja hüpata, ilmuvad need suurusjärgus 50, 40, 30, 20, 10.

Funktsioon pop ()
See funktsioon eemaldab prioriteedijärjestusest kõrgeima prioriteediga väärtuse. Kui võrdluskood on suurem, eemaldab see väikseima väärtusega elemendi. Kui uuesti kutsutakse, eemaldab see järgmise elemendi, millel on ülejäänud väikseim väärtus; uuesti kutsutud, eemaldab see järgmise väikseima väärtuse jne. See tagastab tühimiku. Seda illustreerib järgmine kood:

prioriteedi_järjekord<süsi, vektor<süsi>, suurem<int> >pq;
pq.suruda('');pq.suruda('c');pq.suruda('b');pq.suruda('Ja');pq.suruda('d');

Pange tähele, et liikmefunktsiooni kutsumiseks peab objekti nimele järgnema punkt ja seejärel funktsioon.

Ülemine () funktsioon
The pop () funktsioon eemaldab järgmise kõrgeima prioriteediga väärtuse, kuid ei tagasta seda, nagu pop () on tühine funktsioon. Kasuta ülaosa () funktsiooni, et teada saada kõrgeima prioriteedi väärtus, mis tuleb järgmisena eemaldada. The ülaosa () funktsioon tagastab koopia prioriteedijärjekorra kõrgeima prioriteedi väärtusest. Seda illustreerib järgmine kood, kus kõrgeima prioriteedi järgmine väärtus on väikseim väärtus

prioriteedi_järjekord<süsi, vektor<süsi>, suurem<int> >pq;
pq.suruda('');pq.suruda('c');pq.suruda('b');pq.suruda('Ja');pq.suruda('d');
süsich1=pq.top();pq.popp();
süsich2=pq.top();pq.popp();
süsich3=pq.top();pq.popp();
süsich4=pq.top();pq.popp();
süsich5=pq.top();pq.popp();

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

Väljund on 'a' 'b' 'c' 'd' 'e'.

Funktsioon tühi ()
Kui programmeerija kasutab ülaosa () funktsiooni tühjal prioriteedijärjekorral, pärast edukat kompileerimist saab ta veateate, näiteks:

Segmenteerimise viga(tuum maha visatud)

Seega kontrollige alati enne, kui prioriteedijärjekord pole tühi ülaosa () funktsiooni. The tühi() funktsioon tagastab bool, tõsi, kui järjekord on tühi, ja vale, kui järjekord pole tühi. Seda illustreerib järgmine kood:

prioriteedi_järjekord<int>pq;
inti1= 10; inti2= 30; inti3= kakskümmend; inti4= viiskümmend; inti5= 40;
pq.suruda(i1);pq.suruda(i2);pq.suruda(i3);pq.suruda(i4);pq.suruda(i5);

samas(!pq.tühi())
{
maksma <<pq.top() << '';
pq.popp();
}
maksma << ' n';

Muud eelisjärjekorra funktsioonid

Suurus () Funktsioon
See funktsioon tagastab prioriteedijärjekorra pikkuse, nagu illustreerib järgmine kood:

prioriteedi_järjekord<int>pq;
inti1= 10; inti2= 30; inti3= kakskümmend; inti4= viiskümmend; inti5= 40;
pq.suruda(i1);pq.suruda(i2);pq.suruda(i3);pq.suruda(i4);pq.suruda(i5);

intlen=pq.suurus();
maksma <<len<< ' n';

Väljund on 5.

Funktsioon swap ()
Kui kaks prioriteedijärjestust on sama tüüpi ja sama suurusega, saab selle funktsiooni abil neid vahetada, nagu näitab järgmine kood:

prioriteedi_järjekord<int>pq1;
inti1= 10; inti2= 30; inti3= kakskümmend; inti4= viiskümmend; inti5= 40;
pq1.suruda(i1);pq1.suruda(i2);pq1.suruda(i3);pq1.suruda(i4);pq1.suruda(i5);

prioriteedi_järjekord<int>pqA;
intsee 1= 1; intsee2= 3; intsee 3= 2; intsee4= 5; intsee5= 4;
pqA.suruda(see 1);pqA.suruda(see2);pqA.suruda(see 3);pqA.suruda(see4);pqA.suruda(see5);

pq1.vahetada(pqA);

samas(!pq1.tühi())
{
maksma <<pq1.top() << '';
pq1.popp();
} maksma<<' n';

samas(!pqA.tühi())
{
maksma <<pqA.top() << '';
pqA.popp();
} maksma<<' n';

Väljund 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 () funktsioon sarnaneb tõukefunktsiooniga. Seda illustreerib järgmine kood:

prioriteedi_järjekord<int>pq1;
inti1= 10; inti2= 30; inti3= kakskümmend; inti4= viiskümmend; inti5= 40;
pq1.asuma(i1);pq1.asuma(i2);pq1.asuma(i3);pq1.asuma(i4);pq1.asuma(i5);

samas(!pq1.tühi())
{
maksma <<pq1.top() << '';
pq1.popp();
} maksma<<' n';

Väljund on:

50 40 30 20 10

String Andmed

Stringide võrdlemisel tuleks kasutada stringiklassi, mitte stringi literaalide otsest kasutamist, sest see võrdleks osuti, mitte tegelikke stringe. Järgmine kood näitab, kuidas stringiklassi kasutatakse:

#kaasake
prioriteedi_järjekord<string>pq1;
string s1=string('pliiats'), s2=string('pliiats'), s3=string('harjutuste vihik'), s4=string('õpik'), s5=string('valitseja');

pq1.suruda(s1);pq1.suruda(s2);pq1.suruda(s3);pq1.suruda(s4);pq1.suruda(s5);
samas(!pq1.tühi())
{
maksma <<pq1.top() << '';
pq1.popp();
} maksma<<' n';

Väljund on:

& emsp; õpiku & joonistaja & joonistamispliiats & pintsel & emsp; pliiats & emsp; töövihik

Muud eelisjärjekorra konstruktsioonid

Selge loomine vektorist
Prioriteetset järjekorda saab selgesõnaliselt luua vektorist, nagu näitab järgmine kood:

#kaasake
vektor<int>vtr= {10,30,kakskümmend,viiskümmend,40};

prioriteedi_järjekord<int>pq(vtr.alustada(), vtr.lõpp());

samas(!pq.tühi())
{
maksma <<pq.top() << '';
pq.popp();
} maksma<<' n';

Väljund on: 50 40 30 20 10. Seekord tuleb lisada ka vektoripäis. Konstruktori funktsiooni argumendid võtavad vektori algus- ja lõppviidad. Vektori andmetüüp ja prioriteedijärjekorra andmetüüp peavad olema samad.

Väikseima väärtuse prioriteediks seadmiseks oleks konstruktori deklaratsioon järgmine:

prioriteedi_järjekord<int, vektor<int>, suurem>int> >pq(vtr.alustada(), vtr.lõpp());

Selge loomine massiivist
Prioriteetset järjekorda saab luua massiivist selgesõnaliselt, nagu näitab järgmine kood:

intarr[] = {10,30,kakskümmend,viiskümmend,40};

prioriteedi_järjekord<int>pq(arr, arr+5);

samas(!pq.tühi())
{
maksma <<pq.top() << '';
pq.popp();
} maksma<<' n';

Väljund on: 50 40 30 20 10. Konstruktori funktsiooni argumendid võtavad massiivi algus- ja lõppviidad. arr tagastab alguspointeri, arr+5 tagastab kursori massiivist veidi mööda ja 5 on massiivi suurus. Massiivi andmetüüp ja prioriteedijärjekorra andmetüüp peavad olema samad.

Väikseima väärtuse prioriteediks seadmiseks oleks konstruktori deklaratsioon järgmine:

prioriteedi_järjekord<int, vektor<int>, suurem<int> >pq(arr, arr+5);

Märkus. C ++ -is nimetatakse prioriteedijärjekorda tegelikult adapteriks, mitte ainult konteineriks.

Kohandatud võrdluskood

Kõigi prioriteedijärjekorras olevate väärtuste kasvav või kahanev pole prioriteetide järjekorra ainus võimalus. Näiteks maksimaalse hunniku 11 täisarvu loend on järgmine:

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

Suurim väärtus on 88. Sellele järgnevad kaks numbrit: 86 ja 87, mis on väiksemad kui 88. Ülejäänud numbrid on väiksemad kui need kolm numbrit, kuid mitte päris järjekorras. Loendis on kaks tühja lahtrit. Arvud 84 ja 82 on väiksemad kui 86. Arvud 79 ja 74 on väiksemad kui 87. Arvud 80 ja 81 on väiksemad kui 84. Arvud 64 ja 69 on väiksemad kui 79.

Numbrite paigutus järgib maksimumhunniku kriteeriume-vt hiljem. Sellise skeemi prioriteedi_järjekorra pakkumiseks peab programmeerija esitama oma võrdluskoodi - vt hiljem.

Järeldus

C ++ prioriteedijärjekord on esimene järjekord esimesena. Liikme funktsioon, lükata (), lisab järjekorda uut väärtust. Liikme funktsioon, ülaosa (), loeb järjekorra tippväärtust. Liikme funktsioon, pop (), eemaldab ilma järjekorda ülemist väärtust tagastamata. Liikme funktsioon, tühi(), kontrollib, kas järjekord on tühi. Prioriteet_järjekord erineb aga järjekorrast selle poolest, et järgib mõnda prioriteedialgoritmi. See võib olla suurim, esimesest viimaseks või vähemalt esimesest viimaseks. Kriteeriumid (algoritm) võivad olla ka programmeerija määratletud.