Aby użyć kolejki priorytet_C++, program powinien zaczynać się od kodu takiego jak:
#włączać
#włączać
za pomocą przestrzeń nazwgodziny;
Zawiera bibliotekę kolejek do programu.
Aby kontynuować czytanie, czytelnik powinien mieć podstawową wiedzę o C++.
Treść artykułu
- Podstawowa konstrukcja
- Ważne funkcje członków
- Inne funkcje kolejki priorytetowej
- Dane ciągu
- Inne konstrukcje kolejek priorytetowych
- Wniosek
Podstawowa konstrukcja
Strukturę danych należy najpierw skonstruować, zanim będzie można jej użyć. Konstruowanie tutaj oznacza tworzenie instancji obiektu z klasy kolejki biblioteki. Obiekt kolejki musi wtedy mieć nazwę nadaną mu przez programistę. Najprostsza składnia tworzenia kolejki priorytetowej to:
kolejka priorytetowa<rodzaj>nazwa_kolejki;
W tej składni jako pierwsza usuwana jest największa wartość. Przykładem instancji jest:
kolejka priorytetowa<int>pq;lub
kolejka priorytetowa<zwęglać>pq;
Wektor i deque to dwie struktury danych w C++. Za pomocą jednego z nich można utworzyć kolejkę priorytetową. Składnia tworzenia kolejki priorytetowej ze struktury wektorowej to:
kolejka priorytetowa<typ, wektor<taki sam typ>, porównywać>pq;Przykładem tego wystąpienia jest:
kolejka priorytetowa<int, wektor<int>, mniej<int> >pq;Zwróć uwagę na przerwę między > i > na końcu deklaracji. Ma to na celu uniknięcie pomyłek z >>. Domyślny kod porównania to less, co oznacza, że największa i niekoniecznie pierwsza wartość zostanie usunięta jako pierwsza. Tak więc oświadczenie o stworzeniu można po prostu zapisać jako:
kolejka priorytetowa<int, wektor<int> >pq;Jeśli najmniejsza wartość ma zostać usunięta jako pierwsza, to oświadczenie musi być:
kolejka priorytetowa<int, wektor<int>, większe<int> >pq;Ważne funkcje członków
Funkcja push()
Ta funkcja wypycha wartość, która jest jej argumentem, do kolejki priorytet_. Zwraca pustkę. Poniższy kod ilustruje to:
pq.naciskać(10);
pq.naciskać(30);
pq.naciskać(20);
pq.naciskać(pięćdziesiąt);
pq.naciskać(40);
Ta kolejka priorytetów otrzymała 5 wartości całkowitych w kolejności 10, 30, 20, 50, 40. Jeśli wszystkie te elementy mają zostać usunięte z kolejki priorytetów, pojawią się w kolejności 50, 40, 30, 20, 10.
Funkcja pop()
Ta funkcja usuwa z kolejki priorytet_kolejka wartość o najwyższym priorytecie. Jeśli kod porównania jest większy, usunie element o najmniejszej wartości. Jeśli zostanie wywołany ponownie, usuwa następny element z najmniejszą wartością reszty; wywołana ponownie, usuwa następną najmniejszą obecną wartość i tak dalej. Zwraca pustkę. Poniższy kod ilustruje to:
pq.naciskać('do');pq.naciskać('C');pq.naciskać('b');pq.naciskać('I');pq.naciskać('D');
Zauważ, że aby wywołać funkcję składową, po nazwie obiektu musi znajdować się kropka, a następnie funkcja.
Funkcja top()
ten Muzyka pop () funkcja usuwa następną wartość o najwyższym priorytecie, ale jej nie zwraca, ponieważ Muzyka pop () jest funkcją pustą. Użyj szczyt() funkcji, aby poznać wartość o najwyższym priorytecie, która ma zostać następnie usunięta. ten szczyt() funkcja zwraca kopię wartości o najwyższym priorytecie w kolejce priorytet_kolejka. Poniższy kod, gdzie następna wartość o najwyższym priorytecie jest najmniejszą wartością, ilustruje to
pq.naciskać('do');pq.naciskać('C');pq.naciskać('b');pq.naciskać('I');pq.naciskać('D');
zwęglaćch1=pq.szczyt();pq.Muzyka pop();
zwęglaćch2=pq.szczyt();pq.Muzyka pop();
zwęglaćch3=pq.szczyt();pq.Muzyka pop();
zwęglaćch4=pq.szczyt();pq.Muzyka pop();
zwęglaćch5=pq.szczyt();pq.Muzyka pop();
koszt<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';
Dane wyjściowe to „a” „b” „c” „d” „e”.
Funkcja empty()
Jeśli programista używa szczyt() funkcji na pustej kolejce priorytet_kolejka, po udanej kompilacji otrzyma komunikat o błędzie, taki jak:
Dlatego zawsze sprawdź, czy kolejka priorytetowa nie jest pusta przed użyciem szczyt() funkcjonować. ten pusty() funkcja członkowska zwraca wartość bool, true, jeśli kolejka jest pusta, i false, jeśli kolejka nie jest pusta. Poniższy kod ilustruje to:
kolejka priorytetowa<int>pq;inti1= 10; inti2= 30; inti3= 20; inti4= pięćdziesiąt; inti5= 40;
pq.naciskać(i1);pq.naciskać(i2);pq.naciskać(i3);pq.naciskać(i4);pq.naciskać(i5);
podczas(!pq.pusty())
{
koszt <<pq.szczyt() << '';
pq.Muzyka pop();
}
koszt << ' ';
Inne funkcje kolejki priorytetowej
Funkcja size()
Ta funkcja zwraca długość kolejki priorytetowej, jak ilustruje poniższy kod:
inti1= 10; inti2= 30; inti3= 20; inti4= pięćdziesiąt; inti5= 40;
pq.naciskać(i1);pq.naciskać(i2);pq.naciskać(i3);pq.naciskać(i4);pq.naciskać(i5);
intlen=pq.rozmiar();
koszt <<len<< ' ';
Wyjście to 5.
Funkcja swap()
Jeśli dwie kolejki typu priority_queue są tego samego typu i rozmiaru, można je zamienić za pomocą tej funkcji, jak pokazuje poniższy kod:
inti1= 10; inti2= 30; inti3= 20; inti4= pięćdziesiąt; inti5= 40;
pq1.naciskać(i1);pq1.naciskać(i2);pq1.naciskać(i3);pq1.naciskać(i4);pq1.naciskać(i5);
kolejka priorytetowa<int>pqA;
intto1= 1; intto2= 3; intto3= 2; intto4= 5; intto5= 4;
pqA.naciskać(to1);pqA.naciskać(to2);pqA.naciskać(to3);pqA.naciskać(to4);pqA.naciskać(to5);
pq1.zamieniać(pqA);
podczas(!pq1.pusty())
{
koszt <<pq1.szczyt() << '';
pq1.Muzyka pop();
} koszt<<' ';
podczas(!pqA.pusty())
{
koszt <<pqA.szczyt() << '';
pqA.Muzyka pop();
} koszt<<' ';
Dane wyjściowe to:
5 4 3 2 1
50 40 30 20 10
Miejsce () Funkcja
ten miejsce () funkcja jest podobna do funkcji push. Poniższy kod ilustruje to:
inti1= 10; inti2= 30; inti3= 20; inti4= pięćdziesiąt; inti5= 40;
pq1.umieścić(i1);pq1.umieścić(i2);pq1.umieścić(i3);pq1.umieścić(i4);pq1.umieścić(i5);
podczas(!pq1.pusty())
{
koszt <<pq1.szczyt() << '';
pq1.Muzyka pop();
} koszt<<' ';
Dane wyjściowe to:
50 40 30 20 10
Dane ciągu
Podczas porównywania ciągów należy użyć klasy ciągów, a nie bezpośredniego użycia literałów ciągów, ponieważ porównuje ona wskaźniki, a nie rzeczywiste ciągi. Poniższy kod pokazuje, jak używana jest klasa ciągu:
#włączaćkolejka priorytetowa<strunowy>pq1;
ciąg s1=strunowy('długopis'), s2=strunowy('ołówek')s3=strunowy('ćwiczenia')s4=strunowy(„podręcznik”)s5=strunowy('linijka');
pq1.naciskać(s1);pq1.naciskać(s2);pq1.naciskać(s3);pq1.naciskać(s4);pq1.naciskać(s5);
podczas(!pq1.pusty())
{
koszt <<pq1.szczyt() << '';
pq1.Muzyka pop();
} koszt<<' ';
Dane wyjściowe to:
książeczka tekstowa linijka ołówek ołówek długopis zeszyt ćwiczeń
Inne konstrukcje kolejek priorytetowych
Wyraźne tworzenie z wektora
Kolejkę priorytetową można utworzyć jawnie z wektora, jak pokazuje poniższy kod:
wektor<int>vtr= {10,30,20,pięćdziesiąt,40};
kolejka priorytetowa<int>pq(vtr.rozpocząć(), cz.kończyć się());
podczas(!pq.pusty())
{
koszt <<pq.szczyt() << '';
pq.Muzyka pop();
} koszt<<' ';
Wynik to: 50 40 30 20 10. Tym razem należy również uwzględnić nagłówek wektora. Argumenty funkcji konstruktora przyjmują wskaźniki początku i końca wektora. Typ danych wektora i typ danych priorytet_kolejki muszą być takie same.
Aby najmniejsza wartość była priorytetem, deklaracja dla konstruktora powinna wyglądać następująco:
kolejka priorytetowa<int, wektor<int>, większe>int> >pq(vtr.rozpocząć(), cz.kończyć się()); Wyraźne tworzenie z tablicy
Kolejkę priorytetową można utworzyć jawnie z tablicy, jak pokazano w poniższym kodzie:
kolejka priorytetowa<int>pq(Arr, Arr+5);
podczas(!pq.pusty())
{
koszt <<pq.szczyt() << '';
pq.Muzyka pop();
} koszt<<' ';
Wynik: 50 40 30 20 10. Argumenty funkcji konstruktora przyjmują wskaźniki początkowe i końcowe tablicy. arr zwraca wskaźnik początkowy, arr+5 zwraca wskaźnik tuż za tablicą, a 5 to rozmiar tablicy. Typ danych tablicy i typ danych priorytet_kolejki muszą być takie same.
Aby najmniejsza wartość była priorytetem, deklaracja dla konstruktora powinna wyglądać następująco:
kolejka priorytetowa<int, wektor<int>, większe<int> >pq(Arr, Arr+5);Uwaga: W C++ kolejka_priorytetów jest w rzeczywistości nazywana adapterem, a nie tylko kontenerem.
Niestandardowy kod porównawczy
Posiadanie wszystkich wartości w kolejce priorytetowej rosnącej lub malejącej nie jest jedyną opcją dla kolejki priorytetowej. Na przykład lista 11 liczb całkowitych dla maksymalnej sterty to:
88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69
Najwyższa wartość to 88. Po niej następują dwie liczby: 86 i 87, które są mniejsze niż 88. Pozostałe liczby są mniejsze niż te trzy liczby, ale nie do końca w kolejności. Na liście znajdują się dwie puste komórki. Liczby 84 i 82 są mniejsze niż 86. Liczby 79 i 74 są mniejsze niż 87. Liczby 80 i 81 są mniejsze niż 84. Liczby 64 i 69 są mniejsze niż 79.
Umieszczanie liczb jest zgodne z kryteriami maksymalnej sterty – patrz dalej. Aby zapewnić taki schemat dla kolejki priorytet_kolejka, programista musi dostarczyć własny kod porównawczy – patrz dalej.
Wniosek
Priorytet_kolejki C++ to kolejka typu pierwszy-w-pierwszy-wyszedł. funkcja członkowska, naciskać(), dodaje nową wartość do kolejki. funkcja członkowska, szczyt(), odczytuje najwyższą wartość w kolejce. funkcja członkowska, Muzyka pop (), usuwa bez zwracania najwyższej wartości kolejki. funkcja członkowska, pusty(), sprawdza, czy kolejka jest pusta. Jednak priorytet_kolejka różni się od kolejki tym, że stosuje pewien algorytm priorytetu. Może być największy, od pierwszego do ostatniego lub najmniej, od pierwszego do ostatniego. Kryteria (algorytm) mogą być również zdefiniowane przez programistę.