For at bruge C ++ prioriteret_kø skal programmet begynde med kode som:
#omfatte
#omfatte
ved brug af navnerumtimer;
Det inkluderer købiblioteket i programmet.
For at kunne læse videre skulle læseren have haft en grundlæggende viden om C ++.
Artikelindhold
- Grundlæggende konstruktion
- Vigtige medlemsfunktioner
- Andre prioriterede køfunktioner
- Strengdata
- Andre konstruktioner i prioriteret kø
- Konklusion
Grundlæggende konstruktion
Datastrukturen skal konstrueres først, før den kan bruges. Konstruktion betyder her, at man installerer et objekt fra bibliotekets køklasse. Køobjektet skal derefter have et navn givet af programmereren. Den enkleste syntaks til at oprette en prioritetskø er:
prioritetskø<type>kønavn;
Med denne syntaks fjernes den største værdi først. Et eksempel på instantiering er:
prioritetskø<int>pq;eller
prioritetskø<forkælelse>pq;
Vektoren og deken er to datastrukturer i C ++. Der kan oprettes en prioritetskø med en af dem. Syntaksen til at oprette en prioritetskø fra vektorstrukturen er:
prioritetskø<type, vektor<samme type>, sammenligne>pq;Et eksempel på denne instantiering er:
prioritetskø<int, vektor<int>, mindre<int> >pq;Bemærk forskellen mellem> og> i slutningen af erklæringen. Dette er for at forhindre forveksling med >>. Standard sammenligningskoden er mindre, hvilket betyder, at den største og ikke nødvendigvis den første værdi ville blive fjernet først. Så oprettelseserklæringen kan simpelthen skrives som:
prioritetskø<int, vektor<int> >pq;Hvis den mindste værdi først skal fjernes, skal sætningen være:
prioritetskø<int, vektor<int>, større<int> >pq;Vigtige medlemsfunktioner
Push () funktionen
Denne funktion skubber en værdi, som er dens argument, ind i prioritetskøen. Det returnerer ugyldigt. Følgende kode illustrerer dette:
pq.skubbe(10);
pq.skubbe(30);
pq.skubbe(tyve);
pq.skubbe(halvtreds);
pq.skubbe(40);
Denne prioritetskø har modtaget 5 heltalsværdier i størrelsesordenen 10, 30, 20, 50, 40. Hvis alle disse elementer skal springe ud af prioritetskøen, kommer de ud i størrelsesordenen 50, 40, 30, 20, 10.
Pop () funktionen
Denne funktion fjerner værdien med den højeste prioritet fra prioritetskøen. Hvis sammenligningskoden er større, fjerner den elementet med den mindste værdi. Hvis det kaldes igen, fjernes det næste element med den mindste værdi af resten; kaldet igen, fjerner den den mindste nuværende værdi, og så videre. Det returnerer ugyldigt. Følgende kode illustrerer dette:
pq.skubbe('til');pq.skubbe('c');pq.skubbe('b');pq.skubbe('Og');pq.skubbe('d');
Bemærk, at for at kunne kalde en medlemsfunktion skal objektets navn følges af en prik og derefter funktionen.
Funktionen øverst ()
Det pop () funktion fjerner den næste værdi med højeste prioritet, men returnerer den ikke som pop () er en ugyldig funktion. Brug top() funktion for at kende værdien af højeste prioritet, der skal fjernes næste gang. Det top() funktion returnerer en kopi af værdien af højeste prioritet i prioritetskøen. Den følgende kode, hvor den næste værdi med højeste prioritet er den mindste værdi, illustrerer dette
pq.skubbe('til');pq.skubbe('c');pq.skubbe('b');pq.skubbe('Og');pq.skubbe('d');
forkælelsech1=pq.top();pq.pop();
forkælelsech2=pq.top();pq.pop();
forkælelsech3=pq.top();pq.pop();
forkælelsech4=pq.top();pq.pop();
forkælelsech5=pq.top();pq.pop();
koste<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
Outputtet er 'a' 'b' 'c' 'd' 'e'.
Den tomme () funktion
Hvis en programmør bruger top() funktion på en tom prioritet_kø, efter den vellykkede kompilering, ville han modtage en fejlmeddelelse som:
Så tjek altid, om prioritetskøen ikke er tom, før du bruger top() fungere. Det tom() medlemsfunktion returnerer en bool, sand, hvis køen er tom og falsk, hvis køen ikke er tom. Følgende kode illustrerer dette:
prioritetskø<int>pq;inti1= 10; inti2= 30; inti3= tyve; inti4= halvtreds; inti5= 40;
pq.skubbe(i1);pq.skubbe(i2);pq.skubbe(i3);pq.skubbe(i4);pq.skubbe(i5);
mens(!pq.tom())
{
koste <<pq.top() << '';
pq.pop();
}
koste << ' n';
Andre prioriterede køfunktioner
Størrelsen () Funktion
Denne funktion returnerer længden af prioritetskøen, som følgende kode illustrerer:
inti1= 10; inti2= 30; inti3= tyve; inti4= halvtreds; inti5= 40;
pq.skubbe(i1);pq.skubbe(i2);pq.skubbe(i3);pq.skubbe(i4);pq.skubbe(i5);
intlen=pq.størrelse();
koste <<len<< ' n';
Outputtet er 5.
Swap () funktionen
Hvis to prioritetskøer er af samme type og størrelse, kan de byttes med denne funktion, som følgende kode viser:
inti1= 10; inti2= 30; inti3= tyve; inti4= halvtreds; inti5= 40;
pq1.skubbe(i1);pq1.skubbe(i2);pq1.skubbe(i3);pq1.skubbe(i4);pq1.skubbe(i5);
prioritetskø<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.skubbe(it1);pqA.skubbe(it2);pqA.skubbe(it3);pqA.skubbe(it4);pqA.skubbe(it5);
pq1.bytte rundt(pqA);
mens(!pq1.tom())
{
koste <<pq1.top() << '';
pq1.pop();
} koste<<' n';
mens(!pqA.tom())
{
koste <<pqA.top() << '';
pqA.pop();
} koste<<' n';
Outputtet er:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Emplace () Fuction
Det emplace () funktion ligner push -funktionen. Følgende kode illustrerer dette:
inti1= 10; inti2= 30; inti3= tyve; inti4= halvtreds; inti5= 40;
pq1.placere(i1);pq1.placere(i2);pq1.placere(i3);pq1.placere(i4);pq1.placere(i5);
mens(!pq1.tom())
{
koste <<pq1.top() << '';
pq1.pop();
} koste<<' n';
Outputtet er:
50 40 30 20 10
Strengdata
Når man sammenligner strenge, bør strengklassen bruges og ikke den direkte brug af strengens bogstaver, fordi den ville sammenligne pointer og ikke de faktiske strenge. Følgende kode viser, hvordan strengklassen bruges:
#omfatteprioritetskø<snor>pq1;
streng s1=snor('pen'), s2=snor('blyant'), s3=snor('øvelsesbog'), s4=snor('lærebog'), s5=snor('lineal');
pq1.skubbe(s1);pq1.skubbe(s2);pq1.skubbe(s3);pq1.skubbe(s4);pq1.skubbe(s5);
mens(!pq1.tom())
{
koste <<pq1.top() << '';
pq1.pop();
} koste<<' n';
Outputtet er:
& emsp; lærebog & emsp; lineal & emsp; blyant & emsp; pen & emsp; træningsbog
Andre konstruktioner i prioriteret kø
Eksplicit oprettelse fra en vektor
En prioritetskø kan oprettes eksplicit fra en vektor, som følgende kode viser:
vektor<int>vtr= {10,30,tyve,halvtreds,40};
prioritetskø<int>pq(vtr.begynde(), vtr.ende());
mens(!pq.tom())
{
koste <<pq.top() << '';
pq.pop();
} koste<<' n';
Outputtet er: 50 40 30 20 10. Denne gang skal vektoroverskriften også inkluderes. Argumenterne for konstruktorfunktionen tager vektorens start- og slutpunkt. Datatypen for vektoren og datatypen for prioritetskøen skal være den samme.
For at gøre den mindste værdi til prioriteten ville erklæringen for konstruktøren være:
prioritetskø<int, vektor<int>, større>int> >pq(vtr.begynde(), vtr.ende()); Eksplicit skabelse fra et array
En prioritetskø kan oprettes eksplicit fra et array, som følgende kode viser:
prioritetskø<int>pq(arr, arr+5);
mens(!pq.tom())
{
koste <<pq.top() << '';
pq.pop();
} koste<<' n';
Outputtet er: 50 40 30 20 10. Argumenterne for konstruktorfunktionen tager arrayets start- og slutpunkt. arr returnerer startmarkøren, arr+5 returnerer markøren lige forbi arrayet, og 5 er matrixens størrelse. Datatypen for arrayet og datatypen for prioritetskøen skal være den samme.
For at gøre den mindste værdi til prioriteten ville erklæringen for konstruktøren være:
prioritetskø<int, vektor<int>, større<int> >pq(arr, arr+5);Bemærk: I C ++ kaldes prioriteringskøen faktisk en adapter, ikke kun en beholder.
Tilpasset sammenligningskode
At have alle værdier i prioritetskøen stigende eller alle faldende er ikke den eneste mulighed for prioritetskøen. For eksempel er en liste med 11 heltal for en maksimal bunke:
88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69
Den højeste værdi er 88. Dette efterfølges af to tal: 86 og 87, som er mindre end 88. Resten af tallene er mindre end disse tre tal, men egentlig ikke i orden. Der er to tomme celler på listen. Tallene 84 og 82 er mindre end 86. Tallene 79 og 74 er mindre end 87. Tallene 80 og 81 er mindre end 84. Tallene 64 og 69 er mindre end 79.
Placeringen af tallene følger max-heap kriterierne-se senere. For at tilvejebringe et sådant skema til prioritetskøen, skal programmøren levere sin egen sammenligningskode - se senere.
Konklusion
En C ++ prioriteringskø er en først-i-først-ud-kø. Medlemsfunktionen, skubbe(), tilføjer en ny værdi til køen. Medlemsfunktionen, top(), læser den øverste værdi i køen. Medlemsfunktionen, pop (), fjerner uden at returnere køens topværdi. Medlemsfunktionen, tom(), kontrollerer, om køen er tom. Prioritetskøen adskiller sig imidlertid fra køen, idet den følger en prioritetsalgoritme. Det kan være størst, fra først til sidst eller mindst fra første til sidste. Kriterierne (algoritme) kan også være programmeringsdefinerede.