Kad būtų galima naudoti C ++ prioriteto eilutę, programa turėtų prasidėti tokiu kodu:
#įtraukti
#įtraukti
naudojant vardų sritisvalandų;
Į programą įtraukta eilių biblioteka.
Norėdami toliau skaityti, skaitytojas turėjo turėti pagrindines C ++ žinias.
Straipsnio turinys
- Pagrindinė konstrukcija
- Svarbios nario funkcijos
- Kitos prioritetinės eilės funkcijos
- Eilutės duomenys
- Kitos prioritetinės eilės konstrukcijos
- Išvada
Pagrindinė konstrukcija
Prieš naudojant duomenų struktūrą, ją reikia sukurti. Statyba čia reiškia objekto paleidimą iš bibliotekos eilės klasės. Tada eilės objektas turi turėti programuotojo suteiktą pavadinimą. Paprasčiausia prioritetų eilės kūrimo sintaksė yra tokia:
prioriteto_eilė<tipo>queueName;
Naudojant šią sintaksę, pirmiausia pašalinama didžiausia vertė. Atkartojimo pavyzdys:
prioriteto_eilė<tarpt>pq;arba
prioriteto_eilė<anglis>pq;
Vektorius ir dekas yra dvi duomenų struktūros C ++. Prioriteto eilutę galima sukurti naudojant bet kurį iš jų. Sintaksė, skirta sukurti prioritetinę eilę iš vektorinės struktūros, yra tokia:
prioriteto_eilė<tipas, vektorius<tos pačios rūšies>, palyginti>pq;Šios akimirkos pavyzdys:
prioriteto_eilė<tarpt, vektorius<tarpt>, mažiau<tarpt> >pq;Atkreipkite dėmesį į atotrūkį tarp> ir> deklaracijos pabaigoje. Taip siekiama išvengti painiavos su >>. Numatytasis palyginimo kodas yra mažesnis, tai reiškia, kad didžiausia ir nebūtinai pirmoji vertė būtų pašalinta pirmiausia. Taigi kūrimo pareiškimą galima tiesiog parašyti taip:
prioriteto_eilė<tarpt, vektorius<tarpt> >pq;Jei pirmiausia reikia pašalinti mažiausią vertę, tada teiginys turi būti:
prioriteto_eilė<tarpt, vektorius<tarpt>, didesnis<tarpt> >pq;Svarbios nario funkcijos
Funkcija „push“ ()
Ši funkcija stumia reikšmę, kuri yra jos argumentas, į eilutę prioritetas. Tai grąžina tuštumą. Toliau pateiktas kodas tai iliustruoja:
pq.stumti(10);
pq.stumti(30);
pq.stumti(dvidešimt);
pq.stumti(penkiasdešimt);
pq.stumti(40);
Ši prioriteto eilė gavo 5 sveikojo skaičiaus reikšmes, kurių eilės tvarka yra 10, 30, 20, 50, 40. Jei visi šie elementai turi būti pašalinti iš prioritetinės eilės, jie bus išvardyti 50, 40, 30, 20, 10.
Pop () funkcija
Ši funkcija pašalina prioriteto reikšmę su didžiausiu prioritetu. Jei palyginimo kodas yra didesnis, jis pašalins mažiausios vertės elementą. Jei iškviečiamas dar kartą, jis pašalina kitą elementą, kurio likusi vertė yra mažiausia; paskambinus dar kartą, pašalinama kita mažiausia dabartinė vertė ir pan. Tai grąžina tuštumą. Toliau pateiktas kodas tai iliustruoja:
pq.stumti('iki');pq.stumti(„c“);pq.stumti(„b“);pq.stumti('Ir');pq.stumti(„d“);
Atminkite, kad norint iškviesti nario funkciją, po objekto pavadinimo turi būti po taško, o po to - funkcija.
Viršutinė () funkcija
The pop () funkcija pašalina kitą aukščiausio prioriteto reikšmę, bet negrąžina jos, kaip pop () yra tuštumos funkcija. Naudoti viršuje () funkcija, kad žinotumėte aukščiausio prioriteto, kuris turi būti pašalintas, vertę. The viršuje () funkcija grąžina aukščiausio prioriteto reikšmės kopiją prioriteto_varoje. Toliau pateiktas kodas, kur kita aukščiausio prioriteto reikšmė yra mažiausia vertė
pq.stumti('iki');pq.stumti(„c“);pq.stumti(„b“);pq.stumti('Ir');pq.stumti(„d“);
anglisch1=pq.viršuje();pq.pop();
anglisch2=pq.viršuje();pq.pop();
anglisch3=pq.viršuje();pq.pop();
anglisch4=pq.viršuje();pq.pop();
anglisch5=pq.viršuje();pq.pop();
kaina<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
Išvestis yra „a“ „b“ „c“ „d“ „e“.
Funkcija tuščia ()
Jei programuotojas naudoja viršuje () funkcija tuščioje prioriteto eilutėje, po sėkmingo kompiliavimo jis gaus klaidos pranešimą, pvz .:
Taigi, prieš naudodami visada patikrinkite, ar prioritetų eilė nėra tuščia viršuje () funkcija. The tuščia() nario funkcija grąžina reikšmę, tiesa, jei eilė tuščia, ir klaidingą, jei eilė nėra tuščia. Toliau pateiktas kodas tai iliustruoja:
prioriteto_eilė<tarpt>pq;tarpti1= 10; tarpti2= 30; tarpti3= dvidešimt; tarpti4= penkiasdešimt; tarpti5= 40;
pq.stumti(i1);pq.stumti(i2);pq.stumti(i3);pq.stumti(i4);pq.stumti(i5);
tuo tarpu(!pq.tuščia())
{
kaina <<pq.viršuje() << '';
pq.pop();
}
kaina << ' n';
Kitos prioritetinės eilės funkcijos
Dydis () Funkcija
Ši funkcija grąžina prioritetų eilės ilgį, kaip parodyta šiame kode:
tarpti1= 10; tarpti2= 30; tarpti3= dvidešimt; tarpti4= penkiasdešimt; tarpti5= 40;
pq.stumti(i1);pq.stumti(i2);pq.stumti(i3);pq.stumti(i4);pq.stumti(i5);
tarptlen=pq.dydžio();
kaina <<len<< ' n';
Išėjimas yra 5.
Sukeitimo () funkcija
Jei dvi prioritetinės eilės yra to paties tipo ir dydžio, tada jas galima pakeisti šia funkcija, kaip parodyta šiame kode:
tarpti1= 10; tarpti2= 30; tarpti3= dvidešimt; tarpti4= penkiasdešimt; tarpti5= 40;
pq1.stumti(i1);pq1.stumti(i2);pq1.stumti(i3);pq1.stumti(i4);pq1.stumti(i5);
prioriteto_eilė<tarpt>pqA;
tarpttai1= 1; tarpttai2= 3; tarpttai3= 2; tarpttai4= 5; tarpttai5= 4;
pqA.stumti(tai1);pqA.stumti(tai2);pqA.stumti(tai3);pqA.stumti(tai4);pqA.stumti(tai5);
pq1.apsikeisti(pqA);
tuo tarpu(!pq1.tuščia())
{
kaina <<pq1.viršuje() << '';
pq1.pop();
} kaina<<' n';
tuo tarpu(!pqA.tuščia())
{
kaina <<pqA.viršuje() << '';
pqA.pop();
} kaina<<' n';
Išėjimas yra:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Emplace () Fuction
The įdėti () funkcija yra panaši į stūmimo funkciją. Toliau pateiktas kodas tai iliustruoja:
tarpti1= 10; tarpti2= 30; tarpti3= dvidešimt; tarpti4= penkiasdešimt; tarpti5= 40;
pq1.įdėti(i1);pq1.įdėti(i2);pq1.įdėti(i3);pq1.įdėti(i4);pq1.įdėti(i5);
tuo tarpu(!pq1.tuščia())
{
kaina <<pq1.viršuje() << '';
pq1.pop();
} kaina<<' n';
Išėjimas yra:
50 40 30 20 10
Eilutės duomenys
Lyginant eilutes, reikia naudoti stygų klasę, o ne tiesioginį eilutės literalų naudojimą, nes ji lygintų rodykles, o ne faktines eilutes. Šis kodas parodo, kaip naudojama eilučių klasė:
#įtrauktiprioriteto_eilė<eilutė>pq1;
eilutė s1=eilutė('rašiklis'), s2=eilutė('pieštukas'), s3=eilutė('pratybos'), s4=eilutė(„vadovėlis“), s5=eilutė('valdovas');
pq1.stumti(s1);pq1.stumti(s2);pq1.stumti(s3);pq1.stumti(s4);pq1.stumti(s5);
tuo tarpu(!pq1.tuščia())
{
kaina <<pq1.viršuje() << '';
pq1.pop();
} kaina<<' n';
Išėjimas yra:
& emsp; vadovėlis & liniuotė & pieštukas & pieštukas & pieštukas
Kitos prioritetinės eilės konstrukcijos
Aiškus kūrimas iš vektoriaus
Prioriteto eilę galima aiškiai sukurti iš vektoriaus, kaip parodyta šiame kode:
vektorius<tarpt>vtr= {10,30,dvidešimt,penkiasdešimt,40};
prioriteto_eilė<tarpt>pq(vtr.pradėti(), vtr.galas());
tuo tarpu(!pq.tuščia())
{
kaina <<pq.viršuje() << '';
pq.pop();
} kaina<<' n';
Išvestis: 50 40 30 20 10. Šį kartą taip pat turi būti įtraukta vektorinė antraštė. Konstruktoriaus funkcijos argumentai yra vektoriaus pradžios ir pabaigos rodyklės. Vektoriaus duomenų tipas ir prioriteto_ eilės duomenų tipas turi būti vienodi.
Norint, kad mažiausia vertė būtų prioritetinė, konstruktoriaus deklaracija būtų tokia:
prioriteto_eilė<tarpt, vektorius<tarpt>, didesnis>tarpt> >pq(vtr.pradėti(), vtr.galas()); Aiškus kūrimas iš masyvo
Prioritetų eilę galima aiškiai sukurti iš masyvo, kaip parodyta šiame kode:
prioriteto_eilė<tarpt>pq(arr, arr+5);
tuo tarpu(!pq.tuščia())
{
kaina <<pq.viršuje() << '';
pq.pop();
} kaina<<' n';
Rezultatas yra: 50 40 30 20 10. Konstruktoriaus funkcijos argumentai yra masyvo pradžios ir pabaigos rodyklės. arr grąžina pradžios žymeklį, arr+5 grąžina žymeklį tik už masyvo, o 5 yra masyvo dydis. Masyvo duomenų tipas ir prioriteto_ eilės duomenų tipas turi būti vienodi.
Norint, kad mažiausia vertė būtų prioritetinė, konstruktoriaus deklaracija būtų tokia:
prioriteto_eilė<tarpt, vektorius<tarpt>, didesnis<tarpt> >pq(arr, arr+5);Pastaba: „C ++“ prioriteto eilė iš tikrųjų vadinama adapteriu, o ne tik konteineriu.
Tinkintas palyginimo kodas
Visų prioritetų eilės reikšmių didėjimas arba mažėjimas nėra vienintelė prioritetų eilės parinktis. Pavyzdžiui, 11 sveikųjų skaičių, skirtų maksimaliai krūvai, sąrašas yra toks:
88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69
Didžiausia vertė yra 88. Po to eina du skaičiai: 86 ir 87, kurie yra mažesni nei 88. Likę skaičiai yra mažesni nei šie trys skaičiai, bet tikrai ne eilės tvarka. Sąraše yra dvi tuščios ląstelės. Skaičiai 84 ir 82 yra mažesni nei 86. Skaičiai 79 ir 74 yra mažesni nei 87. Skaičiai 80 ir 81 yra mažesni nei 84. Skaičiai 64 ir 69 yra mažesni nei 79.
Skaičių išdėstymas atitinka maksimalios krūvos kriterijus-žr. Vėliau. Norėdami pateikti tokią schemą prioriteto_kelei, programuotojas turi pateikti savo palyginimo kodą - žr. Vėliau.
Išvada
C ++ prioriteto_eilė yra pirmoji eilėje. Nario funkcija, stumti (), prideda naują vertę eilėje. Nario funkcija, viršuje (), nuskaito didžiausią eilės vertę. Nario funkcija, pop (), pašalinama negrąžinant didžiausios eilės vertės. Nario funkcija, tuščia(), patikrina, ar eilė tuščia. Tačiau prioriteto_eilė skiriasi nuo eilės tuo, kad ji atitinka tam tikrą prioriteto algoritmą. Jis gali būti didžiausias, nuo pirmo iki paskutinio arba mažiausiai nuo pirmo iki paskutinio. Kriterijus (algoritmas) taip pat gali būti programuotojo apibrėžtas.