За да използвате C ++ priority_queue, програмата трябва да започне с код като:
#включва
#включва
използвайки пространство на именатачаса;
Тя включва библиотеката на опашките в програмата.
За да продължи да чете, той трябваше да има основни познания по C ++.
Съдържание на статията
- Основно строителство
- Важни функции на членовете
- Други функции на приоритетна опашка
- Низови данни
- Други конструкции на приоритетни опашки
- Заключение
Основно строителство
Преди да може да се използва, структурата на данните трябва да бъде конструирана. Конструирането тук означава създаване на обект от класа на опашката на библиотеката. След това обектът на опашката трябва да има име, дадено му от програмиста. Най -простият синтаксис за създаване на приоритетна опашка е:
приоритетна_ред<Тип>queueName;
С този синтаксис първо се премахва най -голямата стойност. Пример за екземпляра е:
приоритетна_ред<int>pq;или
приоритетна_ред<char>pq;
Вектор и deque са две структури от данни в C ++. Приоритетна_ред може да бъде създадена с всеки от тях. Синтаксисът за създаване на приоритетна опашка от векторната структура е:
приоритетна_ред<тип, вектор<същия тип>, сравнете>pq;Пример за това създаване е:
приоритетна_ред<int, вектор<int>, по-малко<int> >pq;Обърнете внимание на пропастта между> и> в края на декларацията. Това е за да се предотврати объркване с >>. Кодът за сравнение по подразбиране е по -малък, което означава, че най -голямата, а не непременно първата стойност, ще бъде премахната първа. Така че декларацията за създаване може просто да бъде написана като:
приоритетна_ред<int, вектор<int> >pq;Ако първо трябва да се премахне най -малката стойност, тогава изявлението трябва да бъде:
приоритетна_ред<int, вектор<int>, по-голяма<int> >pq;Важни функции на членовете
Функцията push ()
Тази функция избутва стойност, която е нейният аргумент, в ред_приоритет. Връща се празнота. Следният код илюстрира това:
pq.бутане(10);
pq.бутане(30);
pq.бутане(двайсет);
pq.бутане(петдесет);
pq.бутане(40);
Тази приоритетна_ред е получила 5 цели числа в порядъка на 10, 30, 20, 50, 40. Ако всички тези елементи трябва да бъдат извадени от опашката с приоритет, те ще излязат в реда на 50, 40, 30, 20, 10.
Функцията pop ()
Тази функция премахва от priority_queue стойността с най -висок приоритет. Ако кодът за сравнение е по -голям, тогава той ще премахне елемента с най -малката стойност. Ако бъде извикан отново, той премахва следващия елемент с най -малката стойност на останалите; извикана отново, премахва следващата най -малка налична стойност и т.н. Връща се празнота. Следният код илюстрира това:
pq.бутане('да се');pq.бутане('° С');pq.бутане('b');pq.бутане('И');pq.бутане('д');
Имайте предвид, че за да извикате функция член, името на обекта трябва да бъде последвано от точка, а след това функцията.
Функцията top ()
The поп () функцията премахва следващата стойност с най -висок приоритет, но не я връща, като поп () е функция празнота. Използвай Горна част() функция, за да знаете стойността на най -висок приоритет, която следва да бъде премахната. The Горна част() функцията връща копие на стойността с най -висок приоритет в ред_приоритет. Следващият код, където следващата стойност с най -висок приоритет е най -малката стойност, илюстрира това
pq.бутане('да се');pq.бутане('° С');pq.бутане('b');pq.бутане('И');pq.бутане('д');
charch1=pq.Горна част();pq.поп();
charch2=pq.Горна част();pq.поп();
charch3=pq.Горна част();pq.поп();
charch4=pq.Горна част();pq.поп();
charch5=pq.Горна част();pq.поп();
цена<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<'н';
Изходът е „a“ „b“ „c“ „d“ „e“.
Функцията empty ()
Ако програмист използва Горна част() функция на празна приоритетна_края, след успешното компилиране той ще получи съобщение за грешка като:
Така че, винаги проверявайте дали опашката за приоритет не е празна, преди да използвате Горна част() функция. The празен () функцията член връща bool, true, ако опашката е празна, и false, ако опашката не е празна. Следният код илюстрира това:
приоритетна_ред<int>pq;inti1= 10; inti2= 30; inti3= двайсет; inti4= петдесет; inti5= 40;
pq.бутане(i1);pq.бутане(i2);pq.бутане(i3);pq.бутане(i4);pq.бутане(i5);
докато(!pq.празна())
{
цена <<pq.Горна част() << '';
pq.поп();
}
цена << 'н';
Други функции на приоритетна опашка
Функция size ()
Тази функция връща дължината на приоритетната опашка, както илюстрира следния код:
inti1= 10; inti2= 30; inti3= двайсет; inti4= петдесет; inti5= 40;
pq.бутане(i1);pq.бутане(i2);pq.бутане(i3);pq.бутане(i4);pq.бутане(i5);
intлен=pq.размер();
цена <<лен<< 'н';
Изходът е 5.
Функцията swap ()
Ако две приоритетни_пакети са от един и същи тип и размер, те могат да бъдат заменени от тази функция, както показва следният код:
inti1= 10; inti2= 30; inti3= двайсет; inti4= петдесет; inti5= 40;
pq1.бутане(i1);pq1.бутане(i2);pq1.бутане(i3);pq1.бутане(i4);pq1.бутане(i5);
приоритетна_ред<int>pqA;
intто1= 1; intто2= 3; intit3= 2; intit4= 5; intто5= 4;
pqA.бутане(то1);pqA.бутане(то2);pqA.бутане(it3);pqA.бутане(it4);pqA.бутане(то5);
pq1.размяна(pqA);
докато(!pq1.празна())
{
цена <<pq1.Горна част() << '';
pq1.поп();
} цена<<'н';
докато(!pqA.празна())
{
цена <<pqA.Горна част() << '';
pqA.поп();
} цена<<'н';
Изходът е:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
Empction () Fuction
The emplace () функцията е подобна на функцията push. Следният код илюстрира това:
inti1= 10; inti2= 30; inti3= двайсет; inti4= петдесет; inti5= 40;
pq1.заето място(i1);pq1.заето място(i2);pq1.заето място(i3);pq1.заето място(i4);pq1.заето място(i5);
докато(!pq1.празна())
{
цена <<pq1.Горна част() << '';
pq1.поп();
} цена<<'н';
Изходът е:
50 40 30 20 10
Низови данни
При сравняване на низове трябва да се използва низовият клас, а не директното използване на низовите литерали, тъй като той би сравнявал указатели, а не действителните низове. Следният код показва как се използва низовият клас:
#включваприоритетна_ред<низ>pq1;
низ s1=низ('химилка'), s2=низ('молив'), s3=низ('тетрадка за упражнения'), s4=низ('текстова книга'), s5=низ('владетел');
pq1.бутане(s1);pq1.бутане(s2);pq1.бутане(s3);pq1.бутане(s4);pq1.бутане(s5);
докато(!pq1.празна())
{
цена <<pq1.Горна част() << '';
pq1.поп();
} цена<<'н';
Изходът е:
& emsp; учебник & emsp; линийка & emsp; молив & emsp; химикалка & emsp; тетрадка
Други конструкции на приоритетни опашки
Изрично създаване от вектор
Приоритетна опашка може да бъде създадена изрично от вектор, както показва следният код:
вектор<int>vtr= {10,30,двайсет,петдесет,40};
приоритетна_ред<int>pq(vtr.започнете(), vtr.край());
докато(!pq.празна())
{
цена <<pq.Горна част() << '';
pq.поп();
} цена<<'н';
Изходът е: 50 40 30 20 10. Този път трябва да се включи и заглавката на вектора. Аргументите за функцията конструктор вземат началните и крайните указатели на вектора. Типът данни за вектора и типът за приоритетната_края трябва да са еднакви.
За да се направи най -малката стойност приоритет, декларацията за конструктора ще бъде:
приоритетна_ред<int, вектор<int>, по-голяма>int> >pq(vtr.започнете(), vtr.край()); Изрично създаване от масив
Опашка с приоритет може да бъде създадена изрично от масив, както показва следният код:
приоритетна_ред<int>pq(обр., обр+5);
докато(!pq.празна())
{
цена <<pq.Горна част() << '';
pq.поп();
} цена<<'н';
Резултатът е: 50 40 30 20 10. Аргументите за функцията конструктор вземат началните и крайните указатели на масива. arr връща началния указател, arr+5 връща показалеца точно покрай масива, а 5 е размерът на масива. Типът данни за масива и типът за приоритетната опашка трябва да са еднакви.
За да се направи най -малката стойност приоритет, декларацията за конструктора ще бъде:
приоритетна_ред<int, вектор<int>, по-голяма<int> >pq(обр., обр+5);Забележка: В C ++ приоритетната опашка всъщност се нарича адаптер, а не просто контейнер.
Персонализиран код за сравнение
Наличието на всички стойности в приоритетната опашка възходящо или низходящо не е единствената опция за приоритетната опашка. Например списък с 11 цели числа за максимална купчина е:
88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69
Най -високата стойност е 88. Това е последвано от две числа: 86 и 87, които са по -малки от 88. Останалите числа са по -малки от тези три числа, но всъщност не са в ред. В списъка има две празни клетки. Числата 84 и 82 са по -малки от 86. Числата 79 и 74 са по -малки от 87. Числата 80 и 81 са по -малки от 84. Числата 64 и 69 са по -малко от 79.
Разположението на числата следва критериите за максимална купчина-вижте по-късно. За да предостави такава схема за приоритетна_ред, програмистът трябва да предостави свой собствен код за сравнение - вижте по -късно.
Заключение
C ++ priority_queue е опашка първи-в-първи-изход. Членската функция, push (), добавя нова стойност в опашката. Членската функция, Горна част(), чете горната стойност в опашката. Членската функция, поп (), премахва, без да връща горната стойност на опашката. Членската функция, празен (), проверява дали опашката е празна. Приоритетната_редка обаче се различава от опашката по това, че следва някакъв приоритетен алгоритъм. То може да бъде най -голямо, от първи до последен, или най -малкото, от първо до последно. Критериите (алгоритъмът) също могат да бъдат дефинирани от програмиста.