För att kunna använda C ++ prioritet_kö, bör programmet börja med kod som:
#omfatta
#omfatta
använder sig av namnrymdtimmar;
Det innehåller köbiblioteket i programmet.
För att fortsätta läsa bör läsaren ha haft grundläggande kunskaper i C ++.
Artikelinnehåll
- Grundläggande konstruktion
- Viktiga medlemsfunktioner
- Andra prioriterade köfunktioner
- Strängdata
- Andra prioriterade kökonstruktioner
- Slutsats
Grundläggande konstruktion
Datastrukturen måste konstrueras först innan den kan användas. Konstruktion här innebär att ett objekt skapas från bibliotekets köklass. Köobjektet måste sedan ha ett namn som programmeraren har gett det. Den enklaste syntaxen för att skapa en prioritetskö är:
prioritet_kö<typ>könamn;
Med denna syntax tas det största värdet bort först. Ett exempel på instanseringen är:
prioritet_kö<int>pq;eller
prioritet_kö<röding>pq;
Vektorn och deken är två datastrukturer i C ++. En prioritet_kö kan skapas med någon av dem. Syntaxen för att skapa en prioritetskö från vektorstrukturen är:
prioritet_kö<typ, vektor<samma typ>, jämför>pq;Ett exempel på denna instans är:
prioritet_kö<int, vektor<int>, mindre<int> >pq;Lägg märke till klyftan mellan> och> i slutet av deklarationen. Detta för att förhindra förvirring med >>. Standardjämförelsekoden är mindre, vilket innebär att det största, och inte nödvändigtvis det första värdet, skulle tas bort först. Så skapandeuttalandet kan helt enkelt skrivas som:
prioritet_kö<int, vektor<int> >pq;Om det minsta värdet ska tas bort först måste påståendet vara:
prioritet_kö<int, vektor<int>, större<int> >pq;Viktiga medlemsfunktioner
Push () -funktionen
Den här funktionen skjuter in ett värde, vilket är dess argument, i prioritetskvoten. Det returnerar ogiltigt. Följande kod illustrerar detta:
pq.skjuta på(10);
pq.skjuta på(30);
pq.skjuta på(tjugo);
pq.skjuta på(femtio);
pq.skjuta på(40);
Denna prioritet_kö har fått 5 heltalsvärden i storleksordningen 10, 30, 20, 50, 40. Om alla dessa element ska hoppa ur prioritetskön kommer de ut i storleksordningen 50, 40, 30, 20, 10.
Pop () -funktionen
Den här funktionen tar bort värdet med högsta prioritet från prioritetsköet. Om jämförelsekoden är större tar den bort elementet med det minsta värdet. Om det ropas upp igen tar det bort nästa element med det minsta värdet av resten; kallas igen, det tar bort det näst minsta värdet nuvarande, och så vidare. Det returnerar ogiltigt. Följande kod illustrerar detta:
pq.skjuta på('till');pq.skjuta på('c');pq.skjuta på('b');pq.skjuta på('Och');pq.skjuta på('d');
Observera att för att kunna anropa en medlemsfunktion måste objektets namn följas av en punkt och sedan funktionen.
Funktionen överst ()
De pop () funktion tar bort nästa värde med högsta prioritet, men returnerar det inte som pop () är en ogiltig funktion. Använd topp() funktion för att veta värdet av högsta prioritet som måste tas bort nästa. De topp() -funktionen returnerar en kopia av värdet med högsta prioritet i prioritetsköet. Följande kod, där nästa värde med högsta prioritet är det lägsta värdet, illustrerar detta
pq.skjuta på('till');pq.skjuta på('c');pq.skjuta på('b');pq.skjuta på('Och');pq.skjuta på('d');
rödingch1=pq.topp();pq.pop-();
rödingch2=pq.topp();pq.pop-();
rödingch3=pq.topp();pq.pop-();
rödingch4=pq.topp();pq.pop-();
röding5 kap=pq.topp();pq.pop-();
kosta<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<5 kap<<' n';
Utgången är 'a' 'b' 'c' 'd' 'e'.
Den tomma () -funktionen
Om en programmerare använder topp() -funktionen på en tom prioritets_kö, efter den lyckade sammanställningen skulle han få ett felmeddelande som:
Så kontrollera alltid om prioritetskön inte är tom innan du använder topp() fungera. De tömma() medlemsfunktionen returnerar en bool, true, om kön är tom och falsk om kön inte är tom. Följande kod illustrerar detta:
prioritet_kö<int>pq;inti1= 10; inti2= 30; inti3= tjugo; inti4= femtio; inti5= 40;
pq.skjuta på(i1);pq.skjuta på(i2);pq.skjuta på(i3);pq.skjuta på(i4);pq.skjuta på(i5);
medan(!pq.tömma())
{
kosta <<pq.topp() << '';
pq.pop-();
}
kosta << ' n';
Andra prioriterade köfunktioner
Storleken () Funktion
Denna funktion returnerar längden på prioritetskön, som följande kod illustrerar:
inti1= 10; inti2= 30; inti3= tjugo; inti4= femtio; inti5= 40;
pq.skjuta på(i1);pq.skjuta på(i2);pq.skjuta på(i3);pq.skjuta på(i4);pq.skjuta på(i5);
intlen=pq.storlek();
kosta <<len<< ' n';
Utgången är 5.
Swap () -funktionen
Om två prioriterade_köer är av samma typ och storlek, kan de bytas ut med den här funktionen, som följande kod visar:
inti1= 10; inti2= 30; inti3= tjugo; inti4= femtio; inti5= 40;
pq1.skjuta på(i1);pq1.skjuta på(i2);pq1.skjuta på(i3);pq1.skjuta på(i4);pq1.skjuta på(i5);
prioritet_kö<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.skjuta på(it1);pqA.skjuta på(it2);pqA.skjuta på(it3);pqA.skjuta på(it4);pqA.skjuta på(it5);
pq1.byta(pqA);
medan(!pq1.tömma())
{
kosta <<pq1.topp() << '';
pq1.pop-();
} kosta<<' n';
medan(!pqA.tömma())
{
kosta <<pqA.topp() << '';
pqA.pop-();
} kosta<<' n';
Utgången är:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Emplace () Fuction
De emplace () funktionen liknar push -funktionen. Följande kod illustrerar detta:
inti1= 10; inti2= 30; inti3= tjugo; inti4= femtio; inti5= 40;
pq1.rymma(i1);pq1.rymma(i2);pq1.rymma(i3);pq1.rymma(i4);pq1.rymma(i5);
medan(!pq1.tömma())
{
kosta <<pq1.topp() << '';
pq1.pop-();
} kosta<<' n';
Utgången är:
50 40 30 20 10
Strängdata
När man jämför strängar bör strängklassen användas och inte direkt användning av strängbokstavarna eftersom den skulle jämföra pekare och inte de faktiska strängarna. Följande kod visar hur strängklassen används:
#omfattaprioritet_kö<sträng>pq1;
sträng s1=sträng('penna'), s2=sträng('penna'), s3=sträng('övningsbok'), s4=sträng('textbok'), s5=sträng('linjal');
pq1.skjuta på(s1);pq1.skjuta på(s2);pq1.skjuta på(s3);pq1.skjuta på(s4);pq1.skjuta på(s5);
medan(!pq1.tömma())
{
kosta <<pq1.topp() << '';
pq1.pop-();
} kosta<<' n';
Utgången är:
& emsp; textbok & emsp; linjal & emsp; penna & emsp; pen & emsp; träningsbok
Andra prioriterade kökonstruktioner
Explicit skapelse från en vektor
En prioritetskö kan uttryckligen skapas från en vektor som följande kod visar:
vektor<int>vtr= {10,30,tjugo,femtio,40};
prioritet_kö<int>pq(vtr.Börja(), vtr.slutet());
medan(!pq.tömma())
{
kosta <<pq.topp() << '';
pq.pop-();
} kosta<<' n';
Utgången är: 50 40 30 20 10. Den här gången måste vektorhuvudet också inkluderas. Argumenten för konstruktörsfunktionen tar vektorens start- och slutpekare. Datatypen för vektorn och datatypen för prioritet_kö måste vara desamma.
För att göra det minsta värdet till prioritet skulle deklarationen för konstruktören vara:
prioritet_kö<int, vektor<int>, större>int> >pq(vtr.Börja(), vtr.slutet()); Explicit skapelse från en matris
En prioritetskö kan uttryckligen skapas från en array som följande kod visar:
prioritet_kö<int>pq(arr, arr+5);
medan(!pq.tömma())
{
kosta <<pq.topp() << '';
pq.pop-();
} kosta<<' n';
Utdata är: 50 40 30 20 10. Argumenten för konstruktörsfunktionen tar start- och slutpekarna för matrisen. arr returnerar startpekaren, arr+5 returnerar pekaren precis förbi matrisen och 5 är storleken på matrisen. Datatypen för matrisen och datatypen för prioritet_kö måste vara samma.
För att göra det minsta värdet till prioritet skulle deklarationen för konstruktören vara:
prioritet_kö<int, vektor<int>, större<int> >pq(arr, arr+5);Obs! I C ++ kallas prioritetskvoten faktiskt en adapter, inte bara en behållare.
Anpassad jämförelsekod
Att ha alla värden i prioritetskön stigande eller alla fallande är inte det enda alternativet för prioritetskön. Till exempel är en lista med 11 heltal för en maximal hög:
88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69
Det högsta värdet är 88. Detta följs av två nummer: 86 och 87, som är mindre än 88. Resten av siffrorna är mindre än dessa tre nummer, men inte riktigt i ordning. Det finns två tomma celler i listan. Siffrorna 84 och 82 är färre än 86. Siffrorna 79 och 74 är färre än 87. Siffrorna 80 och 81 är färre än 84. Siffrorna 64 och 69 är färre än 79.
Placeringen av siffrorna följer maxheapkriterierna-se senare. För att tillhandahålla ett sådant schema för prioriteringskvoten måste programmeraren tillhandahålla sin egen jämförelsekod - se senare.
Slutsats
En C ++ prioritet_kö är en först-in-först-ut-kö. Medlemsfunktionen, skjuta på(), lägger till ett nytt värde i kön. Medlemsfunktionen, topp(), läser toppvärdet i kön. Medlemsfunktionen, pop (), tar bort utan att returnera kövärdet. Medlemsfunktionen, tömma(), kontrollerar om kön är tom. Prioritets_kön skiljer sig dock från kön, eftersom den följer en viss prioritetsalgoritm. Det kan vara störst, från första till sista, eller minst, från första till sista. Kriterierna (algoritm) kan också vara programmeringsdefinierade.