Aby bolo možné používať C ++ priority_queue, program by mal začínať kódom ako:
#zahrnúť
#zahrnúť
použitím priestor mienhodiny;
Obsahuje knižnicu frontov do programu.
Aby čitateľ mohol pokračovať v čítaní, mal by mať základné znalosti C ++.
Obsah článku
- Základná konštrukcia
- Dôležité členské funkcie
- Ďalšie prioritné funkcie frontu
- Reťazcové údaje
- Ďalšie stavby prioritných radov
- Záver
Základná konštrukcia
Pred použitím musí byť dátová štruktúra najskôr skonštruovaná. Konštrukcia tu znamená inštanciu objektu z triedy frontu knižnice. Objekt fronty potom musí mať názov, ktorý mu dal programátor. Najjednoduchšia syntax na vytvorenie prioritného frontu je:
priorita_fronta<typ>queueName;
Pri tejto syntaxi sa najskôr odstráni najväčšia hodnota. Príkladom inštancie je:
priorita_fronta<int>pq;alebo
priorita_fronta<char>pq;
Vektor a deque sú dve dátové štruktúry v C ++. S ktoroukoľvek z nich je možné vytvoriť kategóriu priority. Syntax na vytvorenie prioritného frontu z vektorovej štruktúry je:
priorita_fronta<typ, vektor<rovnakého typu>, porovnaj>pq;Príkladom tejto inštancie je:
priorita_fronta<int, vektor<int>, menej<int> >pq;Všimnite si medzery medzi> a> na konci vyhlásenia. Toto má zabrániť zámene s >>. Predvolený porovnávací kód je menší, to znamená, že najskôr sa odstráni najväčšia a nie nevyhnutne prvá hodnota. Takže vyhlásenie o vytvorení môže byť jednoducho napísané ako:
priorita_fronta<int, vektor<int> >pq;Ak sa má najskôr odstrániť najmenšia hodnota, potom musí byť tento príkaz:
priorita_fronta<int, vektor<int>, väčší<int> >pq;Dôležité členské funkcie
Funkcia push ()
Táto funkcia posúva hodnotu, ktorá je jej argumentom, do priority_queue. Vráti sa to prázdne. Nasledujúci kód to ilustruje:
pq.tlačiť(10);
pq.tlačiť(30);
pq.tlačiť(dvadsať);
pq.tlačiť(päťdesiat);
pq.tlačiť(40);
Tento rad priorít získal 5 celočíselných hodnôt v poradí 10, 30, 20, 50, 40. Ak majú byť všetky tieto prvky vysunuté z frontu priorít, potom vyjdú v poradí 50, 40, 30, 20, 10.
Funkcia pop ()
Táto funkcia odstráni z priority_queue hodnotu s najvyššou prioritou. Ak je porovnávací kód väčší, odstráni prvok s najmenšou hodnotou. Ak sa znova zavolá, odstráni nasledujúci prvok s najmenšou hodnotou zvyšku; zavolal znova, odstráni nasledujúcu najmenšiu prítomnú hodnotu atď. Vráti sa to prázdne. Nasledujúci kód to ilustruje:
pq.tlačiť(„do“);pq.tlačiť('c');pq.tlačiť('b');pq.tlačiť(„A“);pq.tlačiť('d');
Upozorňujeme, že na vyvolanie členskej funkcie musí za názvom objektu nasledovať bodka a potom funkcia.
Horná () funkcia
The pop () funkcia odstráni nasledujúcu hodnotu s najvyššou prioritou, ale nevráti ju, ako pop () je prázdna funkcia. Použi hore () funkciu, aby ste poznali hodnotu s najvyššou prioritou, ktorú je potrebné ďalej odstrániť. The hore () funkcia vráti kópiu hodnoty s najvyššou prioritou v rade priorít. Nasledujúci kód, kde ďalšia hodnota s najvyššou prioritou je najnižšia hodnota, to ilustruje
pq.tlačiť(„do“);pq.tlačiť('c');pq.tlačiť('b');pq.tlačiť(„A“);pq.tlačiť('d');
charch1=pq.hore();pq.pop();
charch2=pq.hore();pq.pop();
charch3=pq.hore();pq.pop();
charch4=pq.hore();pq.pop();
charch5=pq.hore();pq.pop();
náklady<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
Výstupom je „a“ „b“ „c“ „d“ „e“.
Funkcia empty ()
Ak programátor používa príponu hore () funkcia na prázdnej fronte priority_, po úspešnej kompilácii sa mu zobrazí chybové hlásenie, ako napríklad:
Pred použitím súboru preto vždy skontrolujte, či nie je prioritný front prázdny hore () funkciu. The prázdny () členská funkcia vracia bool, true, ak je front prázdny, a false, ak front nie je prázdny. Nasledujúci kód to ilustruje:
priorita_fronta<int>pq;inti1= 10; inti2= 30; inti3= dvadsať; inti4= päťdesiat; inti5= 40;
pq.tlačiť(i1);pq.tlačiť(i2);pq.tlačiť(i3);pq.tlačiť(i4);pq.tlačiť(i5);
kým(!pq.prázdny())
{
náklady <<pq.hore() << '';
pq.pop();
}
náklady << ' n';
Ďalšie prioritné funkcie frontu
Funkcia size ()
Táto funkcia vracia dĺžku frontu priorít, ako ukazuje nasledujúci kód:
inti1= 10; inti2= 30; inti3= dvadsať; inti4= päťdesiat; inti5= 40;
pq.tlačiť(i1);pq.tlačiť(i2);pq.tlačiť(i3);pq.tlačiť(i4);pq.tlačiť(i5);
intlen=pq.veľkosť();
náklady <<len<< ' n';
Výstup je 5.
Funkcia swap ()
Ak sú dve fronty priorít rovnakého typu a veľkosti, je možné ich pomocou tejto funkcie zameniť, ako ukazuje nasledujúci kód:
inti1= 10; inti2= 30; inti3= dvadsať; inti4= päťdesiat; inti5= 40;
pq1.tlačiť(i1);pq1.tlačiť(i2);pq1.tlačiť(i3);pq1.tlačiť(i4);pq1.tlačiť(i5);
priorita_fronta<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.tlačiť(it1);pqA.tlačiť(it2);pqA.tlačiť(it3);pqA.tlačiť(it4);pqA.tlačiť(it5);
pq1.vymeniť(pqA);
kým(!pq1.prázdny())
{
náklady <<pq1.hore() << '';
pq1.pop();
} náklady<<' n';
kým(!pqA.prázdny())
{
náklady <<pqA.hore() << '';
pqA.pop();
} náklady<<' n';
Výstupom je:
& 5; 4 & emsp; 3 & emsp; 2 & emsp; 1
& 50; 40 & 30; 20 & 20 & 10
Funkcia emplace ()
The emplace () funkcia je podobná funkcii push. Nasledujúci kód to ilustruje:
inti1= 10; inti2= 30; inti3= dvadsať; inti4= päťdesiat; inti5= 40;
pq1.emplace(i1);pq1.emplace(i2);pq1.emplace(i3);pq1.emplace(i4);pq1.emplace(i5);
kým(!pq1.prázdny())
{
náklady <<pq1.hore() << '';
pq1.pop();
} náklady<<' n';
Výstupom je:
50 40 30 20 10
Reťazcové údaje
Pri porovnávaní reťazcov by mala byť použitá trieda reťazcov, a nie priame použitie reťazcových literálov, pretože by porovnávala ukazovatele a nie skutočné reťazce. Nasledujúci kód ukazuje, ako sa používa trieda reťazcov:
#zahrnúťpriorita_fronta<reťazec>pq1;
reťazec s1=reťazec('pero'), s2=reťazec('ceruzka'), s3=reťazec('cvičebnica'), s4=reťazec('učebnica'), s5=reťazec(„vládca“);
pq1.tlačiť(s1);pq1.tlačiť(s2);pq1.tlačiť(s3);pq1.tlačiť(s4);pq1.tlačiť(s5);
kým(!pq1.prázdny())
{
náklady <<pq1.hore() << '';
pq1.pop();
} náklady<<' n';
Výstupom je:
& emsp; kniha & emsp; pravítko & emsp; ceruzka & emsp; pero & emsp; zošit
Ďalšie stavby prioritných radov
Explicitné vytváranie z vektora
Prioritný front je možné vytvoriť explicitne z vektora, ako ukazuje nasledujúci kód:
vektor<int>vtr= {10,30,dvadsať,päťdesiat,40};
priorita_fronta<int>pq(vtr.začať(), vtr.koniec());
kým(!pq.prázdny())
{
náklady <<pq.hore() << '';
pq.pop();
} náklady<<' n';
Výstup je: 50 40 30 20 10. Tentoraz musí byť zahrnutá aj hlavička vektora. Argumenty pre funkciu konštruktora preberajú počiatočné a koncové ukazovatele vektora. Dátový typ pre vektor a dátový typ pre prioritu_fronta musia byť rovnaké.
Aby bola priorita nastavená na najmenšiu hodnotu, vyhlásenie pre konštruktéra by bolo:
priorita_fronta<int, vektor<int>, väčší>int> >pq(vtr.začať(), vtr.koniec()); Explicitné vytváranie z poľa
Prioritný front je možné vytvoriť explicitne z poľa, ako ukazuje nasledujúci kód:
priorita_fronta<int>pq(arr, arr+5);
kým(!pq.prázdny())
{
náklady <<pq.hore() << '';
pq.pop();
} náklady<<' n';
Výstup je: 50 40 30 20 10. Argumenty pre funkciu konštruktora preberajú počiatočné a koncové ukazovatele poľa. arr vráti počiatočný ukazovateľ, arr+5 vráti ukazovateľ tesne za poľom a 5 je veľkosť poľa. Dátový typ pre pole a dátový typ pre prioritu_fronta musia byť rovnaké.
Aby bola priorita nastavená na najmenšiu hodnotu, vyhlásenie pre konštruktéra by bolo:
priorita_fronta<int, vektor<int>, väčší<int> >pq(arr, arr+5);Poznámka: V jazyku C ++ sa prioritná_trieda v skutočnosti nazýva adaptér, nielen kontajner.
Kód vlastného porovnania
Mať všetky hodnoty v poradí priorít vzostupne alebo zostupne nie je jedinou možnosťou pre poradie priorít. Napríklad zoznam 11 celých čísel pre maximálnu hromadu je:
88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69
Najvyššia hodnota je 88. Nasledujú dve čísla: 86 a 87, ktoré sú menšie ako 88. Ostatné čísla sú menšie ako tieto tri čísla, ale nie sú v úplnom poriadku. V zozname sú dve prázdne bunky. Čísla 84 a 82 sú menšie ako 86. Čísla 79 a 74 sú menšie ako 87. Čísla 80 a 81 sú menšie ako 84. Čísla 64 a 69 sú menšie ako 79.
Umiestnenie čísel sa riadi kritériami max. Haldy-viď neskôr. Na to, aby mohol programátor poskytnúť takú schému priority_queue, musí poskytnúť svoj vlastný porovnávací kód - pozri neskôr.
Záver
Fronta priorít C ++ je front first-in-first-out. Členská funkcia, tlačiť(), pridá novú hodnotu do frontu. Členská funkcia, hore (), prečíta najvyššiu hodnotu vo fronte. Členská funkcia, pop (), odstráni bez vrátenia najvyššej hodnoty frontu. Členská funkcia, prázdny (), skontroluje, či je front prázdny. Rad priority_queue sa však líši od frontu v tom, že dodržiava určitý algoritmus priority. Môže byť najväčší, od prvého po posledný, alebo najmenší, od prvého do posledného. Kritériá (algoritmus) môžu byť tiež definované programátorom.