Pentru a utiliza prioritatea_queue C ++, programul ar trebui să înceapă cu cod ca:
#include
#include
folosind spațiu de numeore;
Acesta include biblioteca de cozi în program.
Pentru a continua citirea, cititorul ar fi trebuit să aibă cunoștințe de bază despre C ++.
Conținutul articolului
- Construcție de bază
- Funcții importante ale membrilor
- Alte funcții de coadă prioritară
- Date șir
- Alte construcții de coadă prioritare
- Concluzie
Construcție de bază
Structura datelor trebuie să fie construită mai întâi înainte de a putea fi utilizată. Construcția aici înseamnă instanțierea unui obiect din clasa de coadă a bibliotecii. Obiectul coadă trebuie să aibă apoi un nume dat de programator. Cea mai simplă sintaxă pentru a crea o coadă prioritară este:
coadă_prioritare<tip>coadăNume;
Cu această sintaxă, cea mai mare valoare este eliminată mai întâi. Un exemplu al instanțierii este:
coadă_prioritare<int>pq;sau
coadă_prioritare<char>pq;
Vectorul și deque sunt două structuri de date în C ++. O prioritate_coadă poate fi creată cu oricare dintre ele. Sintaxa pentru a crea o coadă prioritară din structura vectorială este:
coadă_prioritare<tip, vector<acelasi tip>, comparați>pq;Un exemplu al acestei instanțieri este:
coadă_prioritare<int, vector<int>, Mai puțin<int> >pq;Observați decalajul dintre> și> la sfârșitul declarației. Aceasta este pentru a preveni confuzia cu >>. Codul de comparare implicit este mai mic, ceea ce înseamnă că cea mai mare și nu neapărat prima valoare ar fi eliminată mai întâi. Deci, declarația de creație poate fi scrisă pur și simplu ca:
coadă_prioritare<int, vector<int> >pq;Dacă trebuie eliminată mai întâi cea mai mică valoare, atunci instrucțiunea trebuie să fie:
coadă_prioritare<int, vector<int>, mai mare<int> >pq;Funcții importante ale membrilor
Funcția push ()
Această funcție împinge o valoare, care este argumentul său, în prioritatea_coadă. Revine nul. Următorul cod ilustrează acest lucru:
pq.Apăsați(10);
pq.Apăsați(30);
pq.Apăsați(douăzeci);
pq.Apăsați(cincizeci);
pq.Apăsați(40);
Această prioritate_coadă a primit 5 valori întregi în ordinea a 10, 30, 20, 50, 40. Dacă toate aceste elemente vor fi scoase din coada de prioritate, atunci acestea vor ieși în ordinea a 50, 40, 30, 20, 10.
Funcția pop ()
Această funcție elimină din prioritatea_coadă valoarea cu cea mai mare prioritate. Dacă codul de comparare este mai mare, atunci va elimina elementul cu cea mai mică valoare. Dacă este apelat din nou, elimină următorul element cu cea mai mică valoare a restului; apelat din nou, elimină următoarea cea mai mică valoare prezentă și așa mai departe. Revine nul. Următorul cod ilustrează acest lucru:
pq.Apăsați('la');pq.Apăsați(„c”);pq.Apăsați('b');pq.Apăsați('Și');pq.Apăsați('d');
Rețineți că, pentru a apela o funcție membru, numele obiectului trebuie să fie urmat de un punct, apoi funcția.
Funcția de sus ()
The pop () funcția elimină următoarea valoare cu cea mai mare prioritate, dar nu o returnează, ca pop () este o funcție nulă. Folosește top() funcția pentru a cunoaște valoarea celei mai mari priorități care trebuie eliminată în continuare. The top() funcția returnează o copie a valorii celei mai mari priorități din prioritatea_coadă. Următorul cod, unde următoarea valoare cu cea mai mare prioritate este cea mai mică valoare, ilustrează acest lucru
pq.Apăsați('la');pq.Apăsați(„c”);pq.Apăsați('b');pq.Apăsați('Și');pq.Apăsați('d');
charch1=pq.top();pq.pop();
charch2=pq.top();pq.pop();
charch3=pq.top();pq.pop();
charch4=pq.top();pq.pop();
charch5=pq.top();pq.pop();
cost<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
Ieșirea este „a” „b” „c” „d” „e”.
Funcția goală ()
Dacă un programator folosește top() funcționează pe o coadă de prioritate goală, după compilarea cu succes, el va primi un mesaj de eroare precum:
Deci, verificați întotdeauna dacă coada de prioritate nu este goală înainte de a utiliza top() funcţie. The gol() funcția membru returnează un bool, adevărat, dacă coada este goală și fals dacă coada nu este goală. Următorul cod ilustrează acest lucru:
coadă_prioritare<int>pq;inti1= 10; inti2= 30; inti3= douăzeci; inti4= cincizeci; inti5= 40;
pq.Apăsați(i1);pq.Apăsați(i2);pq.Apăsați(i3);pq.Apăsați(i4);pq.Apăsați(i5);
in timp ce(!pq.gol())
{
cost <<pq.top() << '';
pq.pop();
}
cost << ' n';
Alte funcții de coadă prioritară
Funcția size ()
Această funcție returnează lungimea cozii de prioritate, așa cum ilustrează următorul cod:
inti1= 10; inti2= 30; inti3= douăzeci; inti4= cincizeci; inti5= 40;
pq.Apăsați(i1);pq.Apăsați(i2);pq.Apăsați(i3);pq.Apăsați(i4);pq.Apăsați(i5);
intlen=pq.mărimea();
cost <<len<< ' n';
Ieșirea este de 5.
Funcția swap ()
Dacă două priorități_cozi sunt de același tip și dimensiune, atunci pot fi schimbate de această funcție, după cum arată următorul cod:
inti1= 10; inti2= 30; inti3= douăzeci; inti4= cincizeci; inti5= 40;
pq1.Apăsați(i1);pq1.Apăsați(i2);pq1.Apăsați(i3);pq1.Apăsați(i4);pq1.Apăsați(i5);
coadă_prioritare<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.Apăsați(it1);pqA.Apăsați(it2);pqA.Apăsați(it3);pqA.Apăsați(it4);pqA.Apăsați(it5);
pq1.swap(pqA);
in timp ce(!pq1.gol())
{
cost <<pq1.top() << '';
pq1.pop();
} cost<<' n';
in timp ce(!pqA.gol())
{
cost <<pqA.top() << '';
pqA.pop();
} cost<<' n';
Ieșirea este:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
The emplace () Fuction
The emplace () funcția este similară cu funcția push. Următorul cod ilustrează acest lucru:
inti1= 10; inti2= 30; inti3= douăzeci; inti4= cincizeci; inti5= 40;
pq1.înlocuiți(i1);pq1.înlocuiți(i2);pq1.înlocuiți(i3);pq1.înlocuiți(i4);pq1.înlocuiți(i5);
in timp ce(!pq1.gol())
{
cost <<pq1.top() << '';
pq1.pop();
} cost<<' n';
Ieșirea este:
50 40 30 20 10
Date șir
Când se compară șirurile, ar trebui folosită clasa de șiruri și nu utilizarea directă a literelor șirului, deoarece ar compara indicii și nu șirurile reale. Următorul cod arată cum este utilizată clasa de șiruri:
#includecoadă_prioritare<şir>pq1;
șirul s1=şir('pix'), s2=şir('creion'), s3=şir('carte de exerciții'), s4=şir(„carte de text”), s5=şir('rigla');
pq1.Apăsați(s1);pq1.Apăsați(s2);pq1.Apăsați(s3);pq1.Apăsați(s4);pq1.Apăsați(s5);
in timp ce(!pq1.gol())
{
cost <<pq1.top() << '';
pq1.pop();
} cost<<' n';
Ieșirea este:
& emsp; carte text & emsp; riglă & emsp; creion & emsp; stilou & emsp; caiet de exerciții
Alte construcții de coadă prioritare
Creație explicită dintr-un vector
O coadă de prioritate poate fi creată în mod explicit dintr-un vector așa cum arată următorul cod:
vector<int>vtr= {10,30,douăzeci,cincizeci,40};
coadă_prioritare<int>pq(vtr.începe(), vtr.Sfârșit());
in timp ce(!pq.gol())
{
cost <<pq.top() << '';
pq.pop();
} cost<<' n';
Ieșirea este: 50 40 30 20 10. De data aceasta, trebuie inclus și antetul vector. Argumentele pentru funcția constructor iau indicii de început și de sfârșit ai vectorului. Tipul de date pentru vector și tipul de date pentru prioritatea_coadă trebuie să fie aceleași.
Pentru a face prioritatea cea mai mică valoare, declarația pentru constructor ar fi:
coadă_prioritare<int, vector<int>, mai mare>int> >pq(vtr.începe(), vtr.Sfârșit()); Creație explicită dintr-o matrice
O coadă de prioritate poate fi creată explicit dintr-o matrice, după cum arată următorul cod:
coadă_prioritare<int>pq(arr, arr+5);
in timp ce(!pq.gol())
{
cost <<pq.top() << '';
pq.pop();
} cost<<' n';
Rezultatul este: 50 40 30 20 10. Argumentele pentru funcția constructor iau indicii de început și de sfârșit ai matricei. arr returnează indicatorul de pornire, arr + 5 returnează indicatorul imediat după matrice și 5 este dimensiunea matricei. Tipul de date pentru matrice și tipul de date pentru prioritatea_coadă trebuie să fie aceleași.
Pentru a face prioritatea cea mai mică valoare, declarația pentru constructor ar fi:
coadă_prioritare<int, vector<int>, mai mare<int> >pq(arr, arr+5);Notă: În C ++, prioritatea_coadă se numește de fapt un adaptor, nu doar un container.
Cod de comparare personalizat
A avea toate valorile în coada de prioritate crescătoare sau toate descendente nu este singura opțiune pentru coada de prioritate. De exemplu, o listă de 11 numere întregi pentru o grămadă maximă este:
88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69
Cea mai mare valoare este 88. Urmează două numere: 86 și 87, care sunt mai mici de 88. Restul numerelor sunt mai mici decât aceste trei numere, dar nu chiar în ordine. Există două celule goale în listă. Numerele 84 și 82 sunt mai mici de 86. Numerele 79 și 74 sunt mai mici de 87. Numerele 80 și 81 sunt mai mici de 84. Numerele 64 și 69 sunt mai mici de 79.
Plasarea numerelor respectă criteriile max-heap - vezi mai târziu. Pentru a oferi o astfel de schemă pentru prioritatea_coadă, programatorul trebuie să furnizeze propriul cod de comparare - vezi mai târziu.
Concluzie
O coadă de prioritate C ++ este o coadă first-in-first-out. Funcția de membru, Apăsați(), adaugă o nouă valoare în coadă. Funcția de membru, top(), citește valoarea de sus din coadă. Funcția de membru, pop (), elimină fără a returna valoarea de sus a cozii. Funcția de membru, gol(), verifică dacă coada este goală. Cu toate acestea, priority_queue diferă de coadă, în sensul că urmează un algoritm de prioritate. Poate fi cel mai mare, de la primul la ultim sau, cel puțin, de la primul până la ultimul. Criteriile (algoritmul) pot fi, de asemenea, definite de programator.