Per utilitzar la prioritat_queue de C ++, el programa hauria de començar amb un codi com:
#incloure
#incloure
utilitzant espai de nomshores;
Inclou la biblioteca de cues al programa.
Per continuar llegint, el lector hauria d’haver tingut un coneixement bàsic de C ++.
Contingut de l'article
- Construcció bàsica
- Funcions importants dels membres
- Altres funcions de cua prioritària
- Dades de cadena
- Altres construccions de cua prioritària
- Conclusió
Construcció bàsica
L’estructura de dades s’ha de construir primer abans que es pugui utilitzar. La construcció aquí significa instanciar un objecte des de la classe de cua de la biblioteca. A continuació, l'objecte de cua ha de tenir un nom que el programador li doni. La sintaxi més senzilla per crear una cua de prioritat és:
cua_prioritat<tipus>nom_cua;
Amb aquesta sintaxi, primer s’elimina el valor més gran. Un exemple de la instanciació és:
cua_prioritat<int>pq;o bé
cua_prioritat<char>pq;
El vector i el deque són dues estructures de dades en C ++. Es pot crear una cua de prioritat amb qualsevol d'ells. La sintaxi per crear una cua de prioritat a partir de l'estructura vectorial és:
cua_prioritat<tipus, vector<mateix tipus>, comparar>pq;Un exemple d’aquesta instanciació és:
cua_prioritat<int, vector<int>, menys<int> >pq;Observeu la bretxa entre> i> al final de la declaració. Això és per evitar confusions amb >>. El codi de comparació per defecte és menor, és a dir, primer s’eliminaria el valor més gran i no necessàriament el primer. Per tant, la declaració de creació es pot escriure simplement com:
cua_prioritat<int, vector<int> >pq;Si primer s’elimina el valor mínim, la sentència ha de ser:
cua_prioritat<int, vector<int>, més gran<int> >pq;Funcions importants dels membres
La funció push ()
Aquesta funció empeny un valor, que és el seu argument, a la cua_prioritat. Torna nul. El següent codi ho il·lustra:
pq.empènyer(10);
pq.empènyer(30);
pq.empènyer(20);
pq.empènyer(50);
pq.empènyer(40);
Aquesta prioritat_ca ha rebut 5 valors enters de l'ordre de 10, 30, 20, 50, 40. Si tots aquests elements han de sortir de la cua de prioritat, sortiran de l'ordre de 50, 40, 30, 20, 10.
La funció pop ()
Aquesta funció elimina de la prioritat_cua el valor amb la màxima prioritat. Si el codi de comparació és més gran, eliminarà l'element amb el valor més petit. Si es torna a cridar, elimina l'element següent amb el valor més petit de la resta; cridat de nou, elimina el següent valor més petit present, etc. Torna nul. El següent codi ho il·lustra:
pq.empènyer('A');pq.empènyer('C');pq.empènyer('B');pq.empènyer('I');pq.empènyer('d');
Tingueu en compte que per trucar a una funció membre, el nom de l'objecte ha d'anar seguit d'un punt i, a continuació, de la funció.
Funció top ()
El pop () La funció elimina el següent valor de màxima prioritat, però no el retorna, ja que pop () és una funció buida. Utilitzar el superior() funció per conèixer el valor de màxima prioritat que s’ha d’eliminar a continuació. El superior() La funció retorna una còpia del valor de màxima prioritat a la cua de prioritat. El següent codi, on el següent valor de màxima prioritat és el menor valor, ho il·lustra
pq.empènyer('A');pq.empènyer('C');pq.empènyer('B');pq.empènyer('I');pq.empènyer('d');
charch1=pq.superior();pq.pop();
charch2=pq.superior();pq.pop();
charch3=pq.superior();pq.pop();
charch4=pq.superior();pq.pop();
charch5=pq.superior();pq.pop();
cost<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
La sortida és «a» «b» «c» «d» «e».
La funció empty ()
Si un programador utilitza el fitxer superior() funció en una fila de prioritat buida, després de la compilació reeixida, rebria un missatge d'error com:
Per tant, comproveu sempre si la cua de prioritat no està buida abans d’utilitzar el fitxer superior() funció. El buit() La funció membre retorna un bool, cert, si la cua està buida i fals si la cua no està buida. El següent codi ho il·lustra:
cua_prioritat<int>pq;inti1= 10; inti2= 30; inti3= 20; inti4= 50; inti5= 40;
pq.empènyer(i1);pq.empènyer(i2);pq.empènyer(i3);pq.empènyer(i4);pq.empènyer(i5);
mentre(!pq.buit())
{
cost <<pq.superior() << '';
pq.pop();
}
cost << ' n';
Altres funcions de cua prioritària
Funció size ()
Aquesta funció retorna la longitud de la cua de prioritat, tal com il·lustra el codi següent:
inti1= 10; inti2= 30; inti3= 20; inti4= 50; inti5= 40;
pq.empènyer(i1);pq.empènyer(i2);pq.empènyer(i3);pq.empènyer(i4);pq.empènyer(i5);
intlen=pq.mida();
cost <<len<< ' n';
La sortida és de 5.
La funció swap ()
Si dues cuites de prioritat són del mateix tipus i mida, es poden canviar mitjançant aquesta funció, tal com mostra el codi següent:
inti1= 10; inti2= 30; inti3= 20; inti4= 50; inti5= 40;
pq1.empènyer(i1);pq1.empènyer(i2);pq1.empènyer(i3);pq1.empènyer(i4);pq1.empènyer(i5);
cua_prioritat<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.empènyer(it1);pqA.empènyer(it2);pqA.empènyer(it3);pqA.empènyer(it4);pqA.empènyer(it5);
pq1.intercanviar(pqA);
mentre(!pq1.buit())
{
cost <<pq1.superior() << '';
pq1.pop();
} cost<<' n';
mentre(!pqA.buit())
{
cost <<pqA.superior() << '';
pqA.pop();
} cost<<' n';
La sortida és:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
The emplace () Fuction
El emplace () és similar a la funció push. El següent codi ho il·lustra:
inti1= 10; inti2= 30; inti3= 20; inti4= 50; inti5= 40;
pq1.emplace(i1);pq1.emplace(i2);pq1.emplace(i3);pq1.emplace(i4);pq1.emplace(i5);
mentre(!pq1.buit())
{
cost <<pq1.superior() << '';
pq1.pop();
} cost<<' n';
La sortida és:
50 40 30 20 10
Dades de cadena
En comparar cadenes, s’hauria d’utilitzar la classe de cadena i no l’ús directe dels literals de cadena, perquè compararia els punteres i no les cadenes reals. El següent codi mostra com s’utilitza la classe de cadena:
#inclourecua_prioritat<corda>pq1;
cadena s1=corda('bolígraf'), s2=corda('llapis'), s3=corda('llibre d'exercicis'), s4=corda('llibre de text'), s5=corda('regle');
pq1.empènyer(s1);pq1.empènyer(s2);pq1.empènyer(s3);pq1.empènyer(s4);pq1.empènyer(s5);
mentre(!pq1.buit())
{
cost <<pq1.superior() << '';
pq1.pop();
} cost<<' n';
La sortida és:
& emsp; llibre de text & emsp; regla & emsp; llapis & emsp; llapis & emsp; quadern d’exercicis
Altres construccions de cua prioritària
Creació explícita a partir d’un vector
Es pot crear explícitament una cua de prioritats a partir d’un vector, tal com mostra el codi següent:
vector<int>vtr= {10,30,20,50,40};
cua_prioritat<int>pq(vtr.començar(), vtr.final());
mentre(!pq.buit())
{
cost <<pq.superior() << '';
pq.pop();
} cost<<' n';
La sortida és: 50 40 30 20 10. Aquesta vegada, també s'ha d'incloure la capçalera vectorial. Els arguments per a la funció constructora prenen els indicadors inicial i final del vector. El tipus de dades per al vector i el tipus de dades per a la cola de prioritat han de ser els mateixos.
Per tal de valorar la prioritat com a mínim, la declaració del constructor seria:
cua_prioritat<int, vector<int>, més gran>int> >pq(vtr.començar(), vtr.final()); Creació explícita a partir d’una matriu
Es pot crear explícitament una cua de prioritats a partir d'una matriu, tal com mostra el codi següent:
cua_prioritat<int>pq(arr, arr+5);
mentre(!pq.buit())
{
cost <<pq.superior() << '';
pq.pop();
} cost<<' n';
La sortida és: 50 40 30 20 10. Els arguments per a la funció constructora prenen els indicadors inicial i final de la matriu. arr retorna el punter inicial, arr + 5 retorna el punter just després de la matriu i 5 és la mida de la matriu. El tipus de dades per a la matriu i el tipus de dades per a la prioritat_cua han de ser els mateixos.
Per tal de valorar la prioritat com a mínim, la declaració del constructor seria:
cua_prioritat<int, vector<int>, més gran<int> >pq(arr, arr+5);Nota: A C ++, la prioritat_cua es diu en realitat un adaptador, no només un contenidor.
Codi de comparació personalitzat
Tenir tots els valors a la cua de prioritat ascendent o descendent no és l'única opció per a la cua de prioritat. Per exemple, una llista d'11 enters per a un munt màxim és:
88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69
El valor més alt és 88. A continuació hi ha dos números: 86 i 87, que són inferiors a 88. La resta de números són inferiors a aquests tres números, però no realment en ordre. Hi ha dues cel·les buides a la llista. Els números 84 i 82 són inferiors a 86. Els números 79 i 74 són inferiors a 87. Els números 80 i 81 són inferiors a 84. Els números 64 i 69 són inferiors a 79.
La col·locació dels números segueix els criteris d'emmagatzematge màxim (vegeu més endavant). Per tal de proporcionar aquest esquema per a la prioritat_ca, el programador ha de proporcionar el seu propi codi de comparació (vegeu més endavant).
Conclusió
Una prioritat_queue de C ++ és una cua de primer a primer que surt. La funció membre, push (), afegeix un valor nou a la cua. La funció membre, superior(), llegeix el valor superior de la cua. La funció membre, pop (), elimina sense retornar el valor superior de la cua. La funció membre, buit(), comprova si la cua està buida. Tanmateix, la prioritat_queua difereix de la cua, ja que segueix algun algorisme de prioritat. Pot ser més gran, del primer a l'últim, o menys, del primer a l'últim. Els criteris (algorisme) també es poden definir per programador.