Za uporabo vrstice prioritete C ++ se mora program začeti s kodo, kot je:
#vključi
#vključi
z uporabo imenski prostorure;
V program vključuje knjižnico čakalnih vrst.
Za nadaljevanje branja bi moral bralec imeti osnovno znanje o C ++.
Vsebina članka
- Osnovna gradnja
- Pomembne funkcije člana
- Druge funkcije prednostne čakalne vrste
- Podatkovni niz
- Druge konstrukcije prednostnih čakalnih vrst
- Zaključek
Osnovna gradnja
Pred uporabo je treba najprej sestaviti podatkovno strukturo. Konstrukcija tukaj pomeni ustvarjanje predmeta iz razreda čakalne vrste knjižnice. Objekt čakalne vrste mora imeti potem ime, ki mu ga dodeli programer. Najpreprostejša skladnja za ustvarjanje prednostne čakalne vrste je:
prioritetna čakalna vrsta<tip>ime čakalne vrste;
S to skladnjo se najprej odstrani največja vrednost. Primer instalacije je:
prioritetna čakalna vrsta<int>pq;ali
prioritetna čakalna vrsta<char>pq;
Vektor in deque sta dve podatkovni strukturi v C ++. Z enim od njih je mogoče ustvariti prioritetno čakalno vrsto. Sintaksa za ustvarjanje prioritetne čakalne vrste iz vektorske strukture je:
prioritetna čakalna vrsta<vrsta, vektor<iste vrste>, primerjaj>pq;Primer tega primera je:
prioritetna čakalna vrsta<int, vektor<int>, manj<int> >pq;Upoštevajte vrzel med> in> na koncu izjave. To je za preprečitev zmede s >>. Privzeta koda za primerjavo je manjša, kar pomeni, da bi najprej odstranili največjo in ne nujno prvo vrednost. Tako lahko izjavo o ustvarjanju preprosto zapišemo kot:
prioritetna čakalna vrsta<int, vektor<int> >pq;Če je treba najprej odstraniti najmanjšo vrednost, mora biti stavek naslednji:
prioritetna čakalna vrsta<int, vektor<int>, večji<int> >pq;Pomembne funkcije člana
Funkcija push ()
Ta funkcija potisne vrednost, ki je njen argument, v prioritetno čakalno vrsto. Vrne se v prazno. Naslednja koda ponazarja to:
pqpotiskati(10);
pqpotiskati(30);
pqpotiskati(dvajset);
pqpotiskati(petdeset);
pqpotiskati(40);
Ta vrstica prioritete je prejela 5 celih številk v vrstnem redu 10, 30, 20, 50, 40. Če bodo vsi ti elementi izpuščeni iz prioritetne čakalne vrste, bodo izšli v vrstnem redu 50, 40, 30, 20, 10.
Funkcija pop ()
Ta funkcija odstrani iz vrstice prioritete vrednost z najvišjo prioriteto. Če je koda za primerjavo večja, bo odstranil element z najmanjšo vrednostjo. Če ga ponovno pokličete, odstrani naslednji element z najmanjšo vrednostjo preostalih; ponovno poklicano, odstrani naslednjo najmanjšo prisotno vrednost itd. Vrne se v prazno. Naslednja koda ponazarja to:
pqpotiskati('do');pqpotiskati('c');pqpotiskati('b');pqpotiskati('In');pqpotiskati('d');
Upoštevajte, da mora za klicanje funkcije člana imenu predmeta slediti pika, nato pa funkcija.
Funkcija top ()
The pop () funkcija odstrani naslednjo vrednost najvišje prioritete, vendar je ne vrne, kot pop () je funkcija praznine. Uporabi na vrh () funkcijo, da bi vedeli vrednost najvišje prioritete, ki jo je treba nato odstraniti. The na vrh () funkcija vrne kopijo vrednosti najvišje prioritete v vrstici Priority_queue. To ponazarja naslednja koda, kjer je naslednja vrednost najvišje prioritete najmanjša vrednost
pqpotiskati('do');pqpotiskati('c');pqpotiskati('b');pqpotiskati('In');pqpotiskati('d');
charch1=pqvrh();pqpop();
charch2=pqvrh();pqpop();
charch3=pqvrh();pqpop();
charch4=pqvrh();pqpop();
charpogl=pqvrh();pqpop();
stroški<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<pogl<<' n';
Izhod je 'a' 'b' 'c' 'd' 'e'.
Funkcija empty ()
Če programer uporablja na vrh () funkcijo na prazni prioritetni vrsti, po uspešni kompilaciji bi prejel sporočilo o napaki, kot je:
Zato pred uporabo datoteke vedno preverite, ali čakalna vrsta ni prazna na vrh () funkcijo. The prazno() funkcija member vrne bool, true, če je čakalna vrsta prazna, in false, če čakalna vrsta ni prazna. Naslednja koda ponazarja to:
prioritetna čakalna vrsta<int>pq;inti1= 10; inti2= 30; inti3= dvajset; inti4= petdeset; inti5= 40;
pqpotiskati(i1);pqpotiskati(i2);pqpotiskati(i3);pqpotiskati(i4);pqpotiskati(i5);
medtem(!pqprazno())
{
stroški <<pqvrh() << '';
pqpop();
}
stroški << ' n';
Druge funkcije prednostne čakalne vrste
Funkcija velikost ()
Ta funkcija vrne dolžino prioritetne čakalne vrste, kot prikazuje naslednja koda:
inti1= 10; inti2= 30; inti3= dvajset; inti4= petdeset; inti5= 40;
pqpotiskati(i1);pqpotiskati(i2);pqpotiskati(i3);pqpotiskati(i4);pqpotiskati(i5);
intlen=pqvelikost();
stroški <<len<< ' n';
Izhod je 5.
Funkcija swap ()
Če sta dve vrsti prioritetnih vrst iste vrste in velikosti, ju lahko ta funkcija zamenja, kot prikazuje naslednja koda:
inti1= 10; inti2= 30; inti3= dvajset; inti4= petdeset; inti5= 40;
pq1.potiskati(i1);pq1.potiskati(i2);pq1.potiskati(i3);pq1.potiskati(i4);pq1.potiskati(i5);
prioritetna čakalna vrsta<int>pqA;
intto1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.potiskati(to1);pqA.potiskati(it2);pqA.potiskati(it3);pqA.potiskati(it4);pqA.potiskati(it5);
pq1.zamenjati(pqA);
medtem(!pq1.prazno())
{
stroški <<pq1.vrh() << '';
pq1.pop();
} stroški<<' n';
medtem(!pqA.prazno())
{
stroški <<pqA.vrh() << '';
pqA.pop();
} stroški<<' n';
Izhod je:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Emplace () Fuction
The emplace () funkcija je podobna funkciji push. Naslednja koda ponazarja to:
inti1= 10; inti2= 30; inti3= dvajset; inti4= petdeset; inti5= 40;
pq1.emplace(i1);pq1.emplace(i2);pq1.emplace(i3);pq1.emplace(i4);pq1.emplace(i5);
medtem(!pq1.prazno())
{
stroški <<pq1.vrh() << '';
pq1.pop();
} stroški<<' n';
Izhod je:
50 40 30 20 10
Podatkovni niz
Pri primerjavi nizov je treba uporabiti razred niza in ne neposredne uporabe literal nizov, ker bi primerjal kazalce in ne dejanskih nizov. Naslednja koda prikazuje, kako se uporablja niz nizov:
#vključiprioritetna čakalna vrsta<vrvica>pq1;
niz s1=vrvica('pero'), s2=vrvica('svinčnik'), s3=vrvica('delovni zvezek'), s4=vrvica('učbenik'), s5=vrvica('vladar');
pq1.potiskati(s1);pq1.potiskati(s2);pq1.potiskati(s3);pq1.potiskati(s4);pq1.potiskati(s5);
medtem(!pq1.prazno())
{
stroški <<pq1.vrh() << '';
pq1.pop();
} stroški<<' n';
Izhod je:
& emsp; učbenik & emsp; ravnilo & emsp; svinčnik & emsp; pero & emsp; vadnica
Druge konstrukcije prednostnih čakalnih vrst
Eksplicitno ustvarjanje iz vektorja
Prednostno čakalno vrsto lahko izrecno ustvarite iz vektorja, kot prikazuje naslednja koda:
vektor<int>vtr= {10,30,dvajset,petdeset,40};
prioritetna čakalna vrsta<int>pq(vtr.začeti(), vtr.konec());
medtem(!pqprazno())
{
stroški <<pqvrh() << '';
pqpop();
} stroški<<' n';
Izhod je: 50 40 30 20 10. Tokrat je treba vključiti tudi vektorsko glavo. Argumenti za funkcijo konstruktorja vzamejo začetni in končni kazalec vektorja. Podatkovni tip za vektor in tip podatkov za prioritetno čakalno vrsto morata biti enaka.
Da bi imela prednost najmanjšo vrednost, bi bila izjava za konstruktor:
prioritetna čakalna vrsta<int, vektor<int>, večji>int> >pq(vtr.začeti(), vtr.konec()); Eksplicitno ustvarjanje iz niza
Prednostno čakalno vrsto je mogoče izrecno ustvariti iz matrike, kot prikazuje naslednja koda:
prioritetna čakalna vrsta<int>pq(arr, arr+5);
medtem(!pqprazno())
{
stroški <<pqvrh() << '';
pqpop();
} stroški<<' n';
Izhod je: 50 40 30 20 10. Argumenti za funkcijo konstruktorja vzamejo začetni in končni kazalec matrike. arr vrne začetni kazalec, arr+5 vrne kazalec tik mimo matrike in 5 je velikost matrike. Podatkovni tip za matriko in tip podatkov za prioritetno čakalno vrsto morata biti enaka.
Da bi imela prednost najmanjšo vrednost, bi bila izjava za konstruktor:
prioritetna čakalna vrsta<int, vektor<int>, večji<int> >pq(arr, arr+5);Opomba: V C ++ se prioritetna vrstica dejansko imenuje adapter, ne le vsebnik.
Koda za primerjavo po meri
Vse vrednosti v prednostni čakalni vrsti naraščajoče ali vse padajoče ni edina možnost za prednostno čakalno vrsto. Na primer, seznam 11 celih števil za največji kup je:
88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69
Najvišja vrednost je 88. Temu sledita dve številki: 86 in 87, ki sta manjši od 88. Preostala števila so manjša od teh treh številk, vendar v resnici niso v redu. Na seznamu sta dve prazni celici. Številki 84 in 82 sta manjši od 86. Številki 79 in 74 sta manjši od 87. Številki 80 in 81 sta manjši od 84. Številki 64 in 69 sta manjši od 79.
Postavitev številk sledi kriterijem največjega števila kupcev-glej kasneje. Za zagotovitev takšne sheme za prioritetno čakalno vrsto mora programer zagotoviti svojo primerjalno kodo - glej kasneje.
Zaključek
Prednostna čakalna vrsta C ++ je čakalna vrsta prvi-v-prvi-ven. Funkcija člana, push (), doda novo vrednost v čakalno vrsto. Funkcija člana, zgoraj (), bere najvišjo vrednost v čakalni vrsti. Funkcija člana, pop (), odstrani, ne da bi vrnil najvišjo vrednost čakalne vrste. Funkcija člana, prazno(), preveri, ali je čakalna vrsta prazna. Vendar se prioritetna vrsta razlikuje od čakalne vrste, saj sledi nekemu prioritetnemu algoritmu. Lahko je največji, od prvega do zadnjega ali najmanj, od prvega do zadnjega. Merila (algoritem) je mogoče določiti tudi s programerjem.