For å bruke C ++ prioritet_køen, bør programmet begynne med kode som:
#inkludere
#inkludere
ved hjelp av navneområdetimer;
Det inkluderer købiblioteket i programmet.
For å fortsette å lese, burde leseren ha hatt grunnleggende kunnskap om C ++.
Artikkelinnhold
- Grunnleggende konstruksjon
- Viktige medlemsfunksjoner
- Andre prioriterte køfunksjoner
- Strengdata
- Andre konstruksjoner av prioritetskøer
- Konklusjon
Grunnleggende konstruksjon
Datastrukturen må konstrueres først før den kan brukes. Konstruksjon betyr her å instantere et objekt fra køklassen i biblioteket. Køobjektet må da ha et navn gitt av programmereren. Den enkleste syntaksen for å lage en prioritetskø er:
prioritetskø<type>kønavn;
Med denne syntaksen fjernes den største verdien først. Et eksempel på instantiering er:
prioritetskø<int>pq;eller
prioritetskø<røye>pq;
Vektoren og dekningen er to datastrukturer i C ++. En prioritetskø kan opprettes med en av dem. Syntaksen for å lage en prioritetskø fra vektorstrukturen er:
prioritetskø<type, vektor<samme type>, sammenligne>pq;Et eksempel på denne instantiasjonen er:
prioritetskø<int, vektor<int>, mindre<int> >pq;Legg merke til gapet mellom> og> på slutten av erklæringen. Dette er for å forhindre forvirring med >>. Standard sammenligningskode er mindre, noe som betyr at den største, og ikke nødvendigvis den første verdien, ville bli fjernet først. Så opprettelseserklæringen kan ganske enkelt skrives som:
prioritetskø<int, vektor<int> >pq;Hvis den minste verdien først skal fjernes, må setningen være:
prioritetskø<int, vektor<int>, større<int> >pq;Viktige medlemsfunksjoner
Trykkfunksjonen ()
Denne funksjonen skyver en verdi, som er dens argument, inn i prioritetskøen. Det returnerer ugyldig. Følgende kode illustrerer dette:
pq.trykk(10);
pq.trykk(30);
pq.trykk(tjue);
pq.trykk(femti);
pq.trykk(40);
Denne prioritetskøen har mottatt 5 heltallsverdier i størrelsesorden 10, 30, 20, 50, 40. Hvis alle disse elementene skal dukke ut av prioritetskøen, kommer de ut i størrelsesorden 50, 40, 30, 20, 10.
Pop () -funksjonen
Denne funksjonen fjerner verdien med høyeste prioritet fra prioritetskøen. Hvis sammenligningskoden er større, vil den fjerne elementet med den minste verdien. Hvis det blir ringt igjen, fjernes det neste elementet med den minste verdien av resten; ringt igjen, fjerner den den nest minste verdien til stede, og så videre. Det returnerer ugyldig. Følgende kode illustrerer dette:
pq.trykk('til');pq.trykk('c');pq.trykk('b');pq.trykk('Og');pq.trykk('d');
Vær oppmerksom på at for å kunne ringe en medlemsfunksjon, må navnet på objektet følges av en prikk, og deretter funksjonen.
Funksjonen øverst ()
De pop () funksjon fjerner den neste verdien med høyeste prioritet, men returnerer den ikke som pop () er en ugyldig funksjon. Bruke topp() funksjon for å vite verdien av høyeste prioritet som må fjernes neste gang. De topp() funksjon returnerer en kopi av verdien av høyeste prioritet i prioritetskøen. Følgende kode, der den neste verdien med høyeste prioritet er den minste verdien, illustrerer dette
pq.trykk('til');pq.trykk('c');pq.trykk('b');pq.trykk('Og');pq.trykk('d');
røyech1=pq.topp();pq.pop();
røyech2=pq.topp();pq.pop();
røyech3=pq.topp();pq.pop();
røyech4=pq.topp();pq.pop();
røyech5=pq.topp();pq.pop();
koste<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
Utgangen er 'a' 'b' 'c' 'd' 'e'.
Den tomme () -funksjonen
Hvis en programmerer bruker topp() funksjon på en tom prioritetskø, etter vellykket kompilering, ville han motta en feilmelding som:
Så sjekk alltid om prioritetskøen ikke er tom før du bruker topp() funksjon. De tømme() medlemsfunksjon returnerer en bool, true, hvis køen er tom, og usann hvis køen ikke er tom. Følgende kode illustrerer dette:
prioritetskø<int>pq;inti1= 10; inti2= 30; inti3= tjue; inti4= femti; inti5= 40;
pq.trykk(i1);pq.trykk(i2);pq.trykk(i3);pq.trykk(i4);pq.trykk(i5);
samtidig som(!pq.tømme())
{
koste <<pq.topp() << '';
pq.pop();
}
koste << ' n';
Andre prioriterte køfunksjoner
Størrelsen () Funksjon
Denne funksjonen returnerer lengden på prioritetskøen, slik følgende kode illustrerer:
inti1= 10; inti2= 30; inti3= tjue; inti4= femti; inti5= 40;
pq.trykk(i1);pq.trykk(i2);pq.trykk(i3);pq.trykk(i4);pq.trykk(i5);
intlen=pq.størrelse();
koste <<len<< ' n';
Utgangen er 5.
Swap () -funksjonen
Hvis to prioritetskiler er av samme type og størrelse, kan de byttes med denne funksjonen, slik følgende kode viser:
inti1= 10; inti2= 30; inti3= tjue; inti4= femti; inti5= 40;
pq1.trykk(i1);pq1.trykk(i2);pq1.trykk(i3);pq1.trykk(i4);pq1.trykk(i5);
prioritetskø<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.trykk(it1);pqA.trykk(it2);pqA.trykk(it3);pqA.trykk(it4);pqA.trykk(it5);
pq1.bytte(pqA);
samtidig som(!pq1.tømme())
{
koste <<pq1.topp() << '';
pq1.pop();
} koste<<' n';
samtidig som(!pqA.tømme())
{
koste <<pqA.topp() << '';
pqA.pop();
} koste<<' n';
Utgangen er:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Emplace () Fuction
De emplace () funksjonen ligner på push -funksjonen. Følgende kode illustrerer dette:
inti1= 10; inti2= 30; inti3= tjue; inti4= femti; inti5= 40;
pq1.plassere(i1);pq1.plassere(i2);pq1.plassere(i3);pq1.plassere(i4);pq1.plassere(i5);
samtidig som(!pq1.tømme())
{
koste <<pq1.topp() << '';
pq1.pop();
} koste<<' n';
Utgangen er:
50 40 30 20 10
Strengdata
Når du sammenligner strenger, bør strengklassen brukes og ikke direkte bruk av strengbokstavene fordi den vil sammenligne pekere og ikke de faktiske strengene. Følgende kode viser hvordan strengklassen brukes:
#inkludereprioritetskø<streng>pq1;
streng s1=streng('penn'), s2=streng('blyant'), s3=streng('treningsbok'), s4=streng('lærebok'), s5=streng('Hersker');
pq1.trykk(s1);pq1.trykk(s2);pq1.trykk(s3);pq1.trykk(s4);pq1.trykk(s5);
samtidig som(!pq1.tømme())
{
koste <<pq1.topp() << '';
pq1.pop();
} koste<<' n';
Utgangen er:
& emsp; lærebok & emsp; linjal & emsp; blyant & emsp; penn & emsp; treningsbok
Andre konstruksjoner av prioritetskøer
Eksplisitt skapelse fra en vektor
En prioritetskø kan opprettes eksplisitt fra en vektor slik følgende kode viser:
vektor<int>vtr= {10,30,tjue,femti,40};
prioritetskø<int>pq(vtr.begynne(), vtr.slutt());
samtidig som(!pq.tømme())
{
koste <<pq.topp() << '';
pq.pop();
} koste<<' n';
Utgangen er: 50 40 30 20 10. Denne gangen må vektoroverskriften også inkluderes. Argumentene for konstruktorfunksjonen tar start- og sluttpekene til vektoren. Datatypen for vektoren og datatypen for prioritetskøen må være den samme.
For å gjøre den minste verdien til prioritet, vil erklæringen for konstruktøren være:
prioritetskø<int, vektor<int>, større>int> >pq(vtr.begynne(), vtr.slutt()); Eksplisitt skapelse fra en matrise
En prioritetskø kan opprettes eksplisitt fra en matrise slik følgende kode viser:
prioritetskø<int>pq(arr, arr+5);
samtidig som(!pq.tømme())
{
koste <<pq.topp() << '';
pq.pop();
} koste<<' n';
Utgangen er: 50 40 30 20 10. Argumentene for konstruktorfunksjonen tar start- og sluttpekene til matrisen. arr returnerer startpekeren, arr+5 returnerer pekeren like forbi matrisen, og 5 er størrelsen på matrisen. Datatypen for matrisen og datatypen for prioritetskøen må være den samme.
For å gjøre den minste verdien til prioritet, vil erklæringen for konstruktøren være:
prioritetskø<int, vektor<int>, større<int> >pq(arr, arr+5);Merk: I C ++ kalles prioritert_køen faktisk en adapter, ikke bare en beholder.
Tilpasset sammenligningskode
Å ha alle verdier i prioritetskøen stigende eller alle synkende er ikke det eneste alternativet for prioritetskøen. For eksempel er en liste med 11 heltall for en maksimal haug:
88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69
Den høyeste verdien er 88. Dette etterfølges av to tall: 86 og 87, som er mindre enn 88. Resten av tallene er mindre enn disse tre tallene, men egentlig ikke i rekkefølge. Det er to tomme celler på listen. Tallene 84 og 82 er færre enn 86. Tallene 79 og 74 er færre enn 87. Tallene 80 og 81 er mindre enn 84. Tallene 64 og 69 er færre enn 79.
Plasseringen av tallene følger maks-haugkriteriene-se senere. For å gi et slikt opplegg for prioritetskøen, må programmereren oppgi sin egen sammenligningskode - se senere.
Konklusjon
En C ++ prioritet_kø er en først-inn-først-ut-kø. Medlemsfunksjonen, trykk(), legger til en ny verdi i køen. Medlemsfunksjonen, topp(), leser toppverdien i køen. Medlemsfunksjonen, pop (), fjerner uten å returnere toppverdien til køen. Medlemsfunksjonen, tømme(), sjekker om køen er tom. Prioritetskøen skiller seg imidlertid fra køen, ved at den følger en prioritetsalgoritme. Det kan være størst, fra første til siste, eller minst, fra første til siste. Kriteriene (algoritmen) kan også være programmeringsdefinerte.